Deep Learning for Computing Convergence Rates of Markov Chains
Authors: Yanlin Qu
Jose Blanchet
Peter Glynn
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Markov chains
convergence analysis
Wasserstein distance
neural networks
stochastic optimization
Primary area: probabilistic_methods

Abstract: Convergence rate analysis for general state-space Markov chains is fundamentally important in operations research (stochastic systems) and machine learning (stochastic optimization). 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.

Deep Learning for Computing Convergence Rates of Markov Chains
Yanlin Qu Jose Blanchet
Peter Glynn
Department of Management Science and Engineering
Stanford University [quyanlin,jose jose. blanchet, gaaeeee...gggmnaaaanaata glynm)a@tanfoor..c. edu
Abstract
Convergence rate analysis for general state-space Markov chains is fundamen- tally important in operations research (stochastic systems) and machine learning (stochastic optimization). 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 Calcu- lator (DCDC), the first gencral-purposs 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 (Qu et al. 2023), introduce the Contractive Drift Equation (CDE), the solution of which leads to an explicit convergence bound. Second, we develop an efficient 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 aris- ing from stochastic processing networks well constant step-size stochastic optimization.
Introduction
General state-space Markov chains are indispensable wide array of fields due their flexibility and applicability in modeling random dynamical systems. To analyze the long-term behavior of these Markovian models, estimating the rate of convergence equilibrium is critical. When designing reliable real-world systems (e.g. cloud platforms and manufacturing lines), the faster the convergence, the faster the recovery after disturbances. When designing efficient sample- cample-based algorithms (e.g. stochastic gradient descent (SGD) variants and MCMC), the faster the convergence, the faster the goal attainment. The rate of convergence also appears in MDP-related sample complexity results under the name "mixing time". Although convergence rate estimation is critically important, estimating the convergence rate of even a mildly complex chain can be extremely difficult.
Over the last three decades, significant efforts have been made to bound the convergence of general state-space Markov chains. Most of these works utilize a pair of drift and minorization conditions (D&M) to bound the convergence in terms of the total variation (TV) distance (Meyn et al., 1994
Rosenthal 1995: Jarner and Roberts 2002 Douc et al. 2004 Baxendale 2005] Andrieu al. 2015). The drift condition forces the chain to move towards selected region. On such region, the minorization condition allows the chain regenerate to couple with a stationary version of the chain. This analysis tends to produce overly conservative TV bounds, especially in high-dimensional settings; see (Qin and Hobert 2021) for discussion.
The Wasserstein distance, as measure of convergence to equilibrium, can exhibit better dimension dependence (Qin and Hobert 2022b). In addition, many Markov chains of interest (e.g. constant
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

step- size SGD minimizing convex loss on finite datasets) converge in Wasserstein distance but not in TV distance. Consequently, bounding convergence in Wasserstein distance has steadily gained popularity over the years (Gibbs) 2004 Hairer et al. 2011 Butkovsky 2014 Durmus and Moulines 2015; Durmus et al.) 6] Qin and Hobert 2022a). Most of these works replace the minorization condition with a contraction condition (D&M becomes D&C). After returning to a selected region, two copies of the chain tend to become closer to each other. Both D&M and D&C enforce two conditions in two respective regions. However, partitioning the state space into two distinct regions often leads to suboptimal rates.
Recently, (Qu et al. 2023) introduce the so-called contractive drift condition (CD), single condition enforced on the entire state space, to explicitly bound the convergence in Wasserstein distance. A special case of CD dates back to (Steinsaltz, 1999).. By verifying CD, (Qu et al.) 2023) establish parametrically sharp convergence bounds for stylized Markov chains arising from queueing theory and stochastic optimization (e.g. revealing how step-size, heavy-tailed gradient noise, growth rate and local curvature of objectives affect the convergence of stylized SGD). Although CD may generate better bounds than D&M and D&C for stylized chains (e.g. SGD with iid gradient noise), these methods are generally intended as theoretical tools that can provide closed-form convergence bounds for structured models. For more realistic, less structured chains, computational rather than analytical methods are needed. However, despite of the rapid development of computational power in the past decade, the convergence analysis of general state-space Markov chains is still in the pen-and and-p age.
To launch computational Markov chain convergence analysis, we need a key to switch on the deep learning engine. This paper introduces the Deep Contractive Drift Calculator (DCDC) the first general-purpose sample-base based algorithm for bounding the convergence of general state-space Markov chains. There are two key ideas we develop. The first is to observe that CD, an inequality by definition, is actually an equality by nature (if the inequality has solution, then the corresponding equality also has a solution). Thus, we introduce the Contractive Drift Equation (CDE), an integral equation the solution of which leads to an explicit convergence bound. For the second part, inspired by the success of physics-ine physics-informed informed neural networks (PINNs) in solving PDEs (Sirignano and Spiliopoulos [018)] Raissi et al. 2019), we develop an efficient wew.all-nettwo-ereeeeeeeee two components, DCDC solves CDEs by training neural networks and converts solutions into explicit convergence bounds. DCDC demonstrates the potential of computer-asisted convergence analysis and bridges the gap between deep learning and a traditionally challenging area of mathematical analysis.
CDE solver. By combining these
In high-dimensional spaces, PINNS minimize the integrated residual of a PDE via SGD to find a continuously differentiable function that approximately satisfies the PDE. When applying this idea to solve a CDE, an integral equation, the solving procedure becomes more natural in the following two ways. First, we only assume that the CDE solution is Lipschitz continuous, and neural networks inherently Lipschitz continuous. Second, as SGD is already used to handle the integrated residual, can simultaneously use it to handle the integral in the CDE. After approximately solving the CDE, DCDC needs to convert the solution into a convergence bound, which requires that the solution is uniformly accurate with high probability. This is different from PINNs in the PDE literature since the accuracy is mainly measured in the L2 sense.
The CDE solution is new type of Lyapunov function that provides explicit convergence rates for random dynamical systems. For deterministic dynamical systems, traditional Lyapunov functions play central roles in establishing stability; see (Pukdeboon) 2011) for a review. There is substantial literature on computing traditional Lyapunov functions via neural networks; see (Liu et al.) 2023) and references therein. As pointed out in (Dawson et al. 2022),, survey certificate learning, learned (traditional) Lyapunov functions provide safety certificates for learned control policies (on deterministic dynamical systems). For the control of random dynamical systems, DCDC not only generates safety certificates (CDE solutions) but also quantifies safety levels (convergence rates). Control and performance evaluation of random dynamical systems have become a staple in contemporary data-driven decision making systems, thus underscoring the importance of DCDC.
In short, we summarize our contributions as follows:
We introduce the Deep Contractive Drift Calculator (DCDC), the first general-purpose end-to-end approach that enables the use of deep learning to bound the convergence rate of general state-space Markov chains.
2

---

We perform sample complexity analysis and use DCDC to generate convergence bounds for realistic Markov chains arising in operations research as well as machine learning.
Our DCDC approach discovers features that are exploited by techniques developed study CDs by closed-form methods, such as the wedge shape and the boundary removal technique discussed in (Qu al. 2023).
2
Contractive Drift Equation
Let X be a Markov chain on C R with random mapping representation
X (X+) n
1,
where fr, 's are iid copies of locally Lipschitz random mapping from X' to itself (with probability one, f X + X' is locally Lipschitz).
Example. Let a be positive constant and Z be a square integrable random variable. The SGD with step-size to solve min, E(x / is X X,, ax 7n+1) where 7 's are iid copies of Z, so the corresponding random mapping is f(x) = a(x 2).
Understanding the long-term behavior of X requires estimating how fast Xn converges to Xoc (equilibrium) as n -> oc. The difference between the two distributions is quantified by either total variation (TV) distance or Wasserstein distance. Representative TV convergence bounds (e.g.. g
(X,, ) < Cr") can found in (Meyn et al. 1994 Rosenthal 1995; Baxendale, 2005 Representative Wasserstein convergence bounds (e.g.. WXX,, Xoo) < Cr") can be found in (Hairer jet al., 201T] Durmus and Moulines 2013) Qin and Hobert (022a)). These analytical methods can only handle stylized (structured) Markov chains. The goal of this paper is to introduce the first computational method that can handle realistic (less structured) Markov chains.
The first step to achieve the goal is introducing the contractive drift equation (CDE). The local Lipschitz constant of f at x E X' defined as
|1(xx) - f(x"!l
Df(z)
lim
sup of r (a)
|| x"
where ||-|| is the Euclidean norm and B5(x) fx' || - æ|| < 8). If is differentiable, then
[s + hv) [())|
Df(x) = lim sup h-0 w:]|e[|==
sup
[V = [[V]())]
h
o:| o|||=||=
where V is the Jacobian matrix of and ||-|| becomes the spectral norm when applying to matrices. Basically, (f(x) describes how expansive or contractive f is around æ. With these notations, the
contractive drift condition (CD) in (Qu et al. (023) that leads to computable convergence bounds is
KV(x) A (ED(Z)) S VV<<) U(x), x E X
(1)
where V.U. X' R., are bounded away from zero. In the rest of this paper, we adopt the convention that all functions denoted by U positive and bounded away from zero, i.c. inf U > We use E, to denote the expectation operator conditional on X, x. In ① the subscript is omitted as the initial location clear. By replacing "<" with "=" in ① the contractive drift equation (CDE) is KV = V - U, for which we establish the following existence and uniqueness results. All proofs are the appendix.
Theorem 1. Fix U and suppose that KW S W - U has non-negative finite solution W.. Then
V. (x)
E. Σ U(XT)
IIDMXX-)) TEX
K=D
1=1
finite and satisfies KV, V, U. Furthermore, KV -U has most bounded solution.
Remark. This V. can be interpreted as an average ppace-discounter cumulative reward. Imagine swarm of agents moving according to f. For an agent at xr if D Df(x) < (contraction). then after is applied, there will be more agents around this agent. If all agents around f(xx) share total reward UJJ(x)) then the reward for each them is discounted. From the perspective of particular agent, the procedure is like collecting reward within shrinking ball.
3

---

Deep Contractive Drift Calculator
3.1 Why do we introduce CDE?
Physics-informed neural networks (PINNs) solve a PDE by minimizing its integrated residual (Sirignano and Spiliopoulos) 2018 Raissi et al. 2019). we want use this idea solve KV I U, then the integrated residual is
T(O) / (KVi(1) Vo(ω) + (+)) Mx)de x
where h is positive density and (Vo A ) is neural network. Note that the residual at is positive if and only if (x) Vo(z) (x)) By letting X, have distribution h,
[()) = E [B (X))
Vo(Xo) + Xoo))
which is expectation of non- non-linear function of conditional expectation. Minimizing I(0) is conditional stochastic optimization problem (CSO). In CSO, the sample-average gradient is biased (Hu al. 2020b), which leads Fortunately, y. if we aim at solving KV = V U (CDE) instead of KV < V U (CD), then there exists simple unbiased gradient estimator. Now we briefly derive this estimator. For CDE, the integrated residual becomes
high sample complexity for convergence (Hu et al. (020a).
1(0) = / -xVo(=)-V((=)++))) h(x)dr
-
with its gradient
(()
=2E [E (FT
-2EB ([D((X))V6(((())) -1060:/0400000112222000110001000 [Xo]
-2 (X) +2C6==0(((///112222003333-000000
where fi and f-1 are iid copies of while V/ -Vo is computed via backpropagation. This expression allows us estimate (0) without any bias. summary, the inequality (CD) is enough to bound the convergence, but the equality (CDE) turns out to be easier to establish (via deep learning).
3.2 DCDC
Given the above discussion, standard application of SGD is enough simultaneously handle the integrated residual as well as the integral in the CDE, resulting in the following simple algorithm, Deep Contractive Drift Calculator, the first general-purpose sample-based algorithm to bound the convergence of general state-space Markov chains.
Algorithm Deep Contractive Drift Calculator (DCDC)
Require: Step-size number of iterations T, neural network (Vo 0 E θ). initialization On for 1. E [0, .... 1) do
sample (Xp, f-1
compute (0.)
2 (Xo (f. Ve, (Xo) (X VG (Xx)
update 0++1 = 02 ai (SGD or its variants)
end for convert Vo, into convergence bound (Theorem and Theorem
The conversion will be discussed in the next two subsections. In the current subsection, we show the validity of approximating CDE solutions via neural networks. the following, we use ||-1l.gg to denote the sup norm of functions on X.

---

Theorem 2. If X is compact. ||D loo is finite, and V. in 2 is finite and continuous, then for any e 0, there exists a neural network VV ) and its realization Vo, such that
|KV Vo. Ull <.
Although DCDC solves CDEs on compact sets, can be applied Markov chains on non-compact sets that have compact absorbing sets (e.g. SGD for regularized problems). For chains without compact absorbing set, extending DCDC to bound their convergence left for future research, but here we describe natural strategy to do so. In general, a Markov chain spends most of its time on some large compact set where the chain may have complex dynamics. When the chain is outside C, it typically has strong tendency to return. Therefore, to extend DCDC, we can (i) search some parametric family (e.g. (a(z) = x Az) to establish a CD outside C (capturing the return tendency); (ïi) apply DCDC to obtain CDE solution on C' (capturing the complex dynamics); (iii) stitch them together to obtain a global CD. Comparing the large set here with the small set (Meyn and Tweedie 2009) in D&M D&C illustrates the advantage of computational methods over analytical ones. The size of the large set is determined by the approximation capability of neural networks, but the size of the small set is determined by the minorization contraction condition (the two conditions often require the small set to be very small).
3.3 Practical convergence bounds with exponential rates
Now we discuss how to convert KV < V - U' into convergence bounds with exponential rates in Wasserstein distance. To begin, we recall the definition of the Wasserstein distance. Let P(2) be the set of probability measures on X' equipped with its Borel sigma-algebra. The Wasserstein distance between μ. V E P(X) is
- inf TEC(u,)) Xxx
/xxx ||x yll (dI, dy)
where
C(H,V) (TEE)))))) =();)) ((-), ((x,))=v())
is the set of all couplings of μ and v. Given two random variables Zı and Z2, we use W(Z1, Z2) to denote the Wasserstein distance between their marginal distributions.
Theorem 3. Suppose that X is convex and that KV S. V - - holds with sup V < oo. If
E | Xill oc, then X has a unique stationary distribution X with
E | X1ll (Xo + UX1 (1X1-1 Xo))
W(Xn, Xxo) S Cr", r 2 U/ C
inf U (inf v/sup// V)
where U is a U10,1 1] random variable independent of Xo and X1.
Given U, the exponential rate is determined by the magnitude of V. The smaller the V, the faster the convergence. Given Xo. the pre-multiplier C' can be easily computed by simulating the first transition (from Xo to X1).
In Theorem 3 of (Qu et al. 2023), convergence bounds with exponential rates are straightforwardly derived from V < rV where < 1, one might wonder why we need the less straightforward Theorem 3 here. This is because KV < rV is not suitable for PINN-like solvers. In Theorem 3 we solve K V V U and compute the exponential rate from the solution V. However, for KV = rV, we need the answer (the exponential rate r) to write down the question (the equation to solve and the corresponding loss to minimize), which is cireular. Of course, we may try solving KV = rV for different values of r, but turns out that it is very hard for DCDC to converge even for very conservative (close to 1) r's. Here is explanation. Unlike KV V U, which has solution as long as KV < V - U has one (Theorem T. KV = rV may not have a solution even when KV < rV has one. However, it is not hard to show that KV rV has (formal) solution
Vx(x)
E
(1/r)* II ID X
Comparing with V. in 2 (Xx) is replaced by exponentially exploding (1/r)*, Back to KV = rV, its solution (if there is any) should be the above expression without the summation but with k: + oo (as a limit), which suggests that the solution may have large magnitude, making difficult to approximate.
5

---

3,4 Practical convergence bounds with polynomial rates
Now we discuss how to generate convergence bounds with polynomial rates using DCDC. The key is to iteratively solve sequence of CDEs. For example, given Vo, we first solve VV = Ví Vo to obtain V12 Then we solve KV2 V/2 V1 obtain Vz. These two CDEs together lead to an O(1nn) convergence bound.
Theorem 4. Suppose that X' convex and that there exist f O < inf Vo sup Vn, < oo and KVK+1 I VV++1 V& for k = O.... 1. If |Xo X1 || c0,
functions Vo. Vi.... Vn such that
then X has unique stationary distribution X x0 with
E X X1 Vm (Xu + +X( - Xo))
W(X,, Xxo)
inf Vo II (1 + n1+n/k)
where U is a U00, 1] random variable independent of Xo and X1.
The expectation in the numerator can be easily computed by simulating the first transition, while the product in the denominator is basically n as n2 - 00.
In Theorem 1 of (Qu et al., 2023), convergence bounds with polynomial rates (O(1/n²-1))
derived from KV I V UT"V 11i/v111 1-1m 1/m paired with KU < U.
might wonder why need so many CDs in Theorem 4 here. This is because KV < V U1/mVL-1/m is designed for the pen-and-paper setting where directly establishing a sequence of CDs is difficult. Given KV S V f/1/m/1--/// many inequalities are applied extract a CD sequence from this single special CD, resulting in large constants in convergence bounds. DCDC makes it possible to directly establish a sequence CDs (by consecutively solving CDEs). In this setting, we can use Theorem to obtain better convergence bounds. To be specific, compared with our Theorem 4 the result in QQu al. 2023 has an extra factor m //m!.
Sample Complexity
As a numerical solver, DCDC solves CDEs approximately. Let V = Ve, be the output of DCDC. We should not expect KV = V - U to hold exactly. Even V an exact solution, the exactness is hard to verify as KV is an expectation and the domain c Rd is not finite set. As establishing convergence bounds requires CDDs exactly hold everywhere, given N iid copies of f to estimate K and M = (.1,..., ,FM) uniformly sampled from X', we can (i) establish
N
A Rx
1 N
E k=1
DI(())V((A)))) & (<c) - (((), x 3EM
where ú may be smaller than U (e.g. if V is supposed solve V - KV U = then Ú in[ KN V)); (ii) claim that KV < V - + holds everywhere with probability at least 1 where c, 8 >> (iii) convert KV < <V Ú Ü- + into convergence bound. To have M, N large enough to make the claim in (ii), we need the following sample complexity result.
Theorem 5. Suppose that (i) X is compact; (üi) V, U are bounded and Lipschitz: (üi) EDf² ED2 < where Df is the Lipschitz constant of f and D2 is the Lipschitz constant Df. Given 5 > 0, we can choose = (1()o)((1))((())))) and N =
to have
sup (KV())-VVL)) + U(x)) S sup xEeX
(x + U(x)) +c)
ZEM
Since the exponential rate of convergence in Theorem 3 is r 1 inf inf in Theorem 5 also
provides the sample complexity for estimating the exponential rate. Specifically, with probability at
least 1 - 6, the exponential rate f.N computed from KvV < - on M, which may not be valid exponential rate, is e-close valid exponential rate r. (given by KV < V - + on X²).
worth noting that in terms of sample complexity. Theorem 5 guarantees a DCDC certificate (and thus convergence bound to stationarity) with high probability with an efficient parametric (11/ rate in terms of the number of samples (namely, the bound holds with high probability

---

up to an eπror of order (21/N Once samples are generated, M = ((1/e)) points are chosen for the empirical evaluation. Thus, the total complexity (both terms of number of evaluations and number of samples is 0(1/2) + Ó(1/e). A related literature on parametric integration (i.e. learning a Markov transition kernel that maps Lipschitz functions to continuous functions on the d-dimensional cube) provides a lower bound of order Ó(1/c"), (Heinrich and Sindambiwe, 1999). Although these results are suggestive, they cannot be applied directly because we assume a random mapping representation, which provides additional structure. We plan to study the lower bounds in future work.
Numerical Examples
5.1 Mini-batch SGD for logistic regression with regularization
Having established the theoretical foundation of DCDC, we now utilize it to generate convergence bounds for Markov chains of interest that too hard for pen-and -aper analysis. To begin, bound the convergence of a constant step-size mini-batch SGD that minimizes the cross-entropy loss over finite dataset with L2 regularization.
Let (x1, "................... Um) be m data points where 2; 1-1/2,1/2|" and ys E (0, 1}. To perform regularized logistic regression, we want to choose b E R2² to minimize
m
Σ (y lo p. + (1 - yi) log(1 - p.)) + 2m |bb
p; = a(b' x:) = exp( bT;;)
171
where is the regularization parameter. The random mapping representation of the corresponding SGD with step-size and batch-size is
((b) -h - >a/m)) + (a/B3
Σ iEB
[y - a abb (bTx)))] x,
where B with |B| = 3 is uniformly sampled from {l...., m]. Thanks to the regularization, the
chain has compact absorbing set. In fact, the chain cannot escape from B Bm/(AVZ) (0). The local Lipschitz constant of f(b) is
Df(b)= = (1 --aa/mmm---- - (a/3)
Ld'(6" x, 2
< 1 - -aa/m
iEB
where ||-||| = suPe:||=|==1 ||A is the spectral norm. This demonstrates that the L2 regularization makes the chain contractive [[f(bi) f(b2))l < (1 >a/m) |lb b2ll. However, since the regu- larization parameter is chosen via cross-validation in a separate validation process, it is useful to obtain a contraction rate that is uniform in the regularization parameter. This rate is brought by the second term in (b) we refer to this contribution as the intrinsic convergence rate. However, is need
challenging to analyze the spectrum of this state-dependent bata-based random matrix, DCDC. The code is available in the supplementary material. Each training procedure in this paper was completed within ten minutes
M2 MacBook Air with 8GB RAM.
For the dataset, we set m 100 and uniformly generate 100 x; s. For each x; its label y follows Ber(0.9) or Ber(0.1). (0. depending upon which coordinate of z; is larger. For the SGD, we set the regularization parameter À = 1, step-size a = 0.1, and batch-size 3 10. For DCDC, we run IM Adam steps to train single-layer network with width 1000 and sigmoid activation. We also experiment with deeper networks with the same amount of neurons, and the results are similar.
As demonstrated in Figure 5.1 the single-layer network can already accurately solve the CDE KV = V - 0.1. The learned solution V is on the left while the estimated difference RV - V is on the right. Aiming KV <V- 0.1, we get KV < V 0.0986. This leads to exponential rate 1 - 1.07 10 (Theorem 3) where 1 x 10-3 corresponds to the regularization contribution, while 7 x 10-5 corresponds to the intrinsic rate. Now we briefly discuss how the surface in Figure 5.1 (left) leads to the intrinsic rate. From the expression of Df(b), we know that the intrinsic contraction concentrates around the center. To make it contribute to the overall convergence, needs to be spread. The surface in Figure 5.1 (left) provides the media to spread: (i) for points not
7

---

40
Figure I: Left: The learned solution V of KV -V for the mini-batch SGD, with maximum 91.87. Right: The estimated difference KV V. with maximum -0.0986, mean -0.9999, standard deviation 0.0003.
at the center, the sunken surface creates drift E, (X,) < V(x); (ii) however, for points at the center, the sunken surface creates an anti-drift E2 (X > ((x), but it overcome by the strong contraction E, Df (X1) < V(x). In this way, the strong contraction is spread (in the form contractive drift, which leads the intrinsic rate. conclude this example, when Xo = O, we compute the pre-multiplier C 8.1, which leads convergence bound
of drift) to overall improve
W(X,. xx) < 8.1(1 - 1.07 10 -3n.
5.2 Tandem fluid networks
In the above SGD example, contraction plays the leading role. Now we consider a tandem fluid network (Kella and Whitt 1992) where drift plays the leading role. Let 81 and 82 be two stations with buffer capacity that can process fluid workload at rates and r2, respectively. External fluid only arrives at $1 and is processed by 81 then 82. Assume that the external imput follows compound renewal process where random amount of fluid Z arrives after random length of time T has passed since the last arrival. r < 72, then 82 is always empty, so we let T1 > 72. Let X the remaining workload vector after each arrival. Its random mapping representation is
f( x2) = (anin(xx--11))) +2, c), (2in(22- + +(1 -72) min(T,
where 21 decreases rate F1 until it is empty while 22 increases at rate (r) 722 until is empty. Basically, within [0, c]2, the chain follows northwest-then the---outhh-hhhhhh path for time and then jumps east by amount Z. This chain has simple local Lipschitz constant D fz( x2) [[T < (I1 + #2)/r2), obtained as an infinitesimal ball around (x1,22) collapses to a single point when the system is depleted before the next arrival. As result, drift plays the leading role contraction only happens around the origin.
For the tandem network, we set the buffer capacity 1, processing rates (r1, (1.1, 1.0), interarrival time (0, 0.2] and arriving amount U 0.1] (the stability condition E.Z < E2T)). For DCDC, we run 1M Adam steps to train a double-layer network with width 40 and sigmoid activation.
Although a slightly deeper network is trained, the result in Figure 5.2 (left) is almost a plane. Now we briefly explain why this is the correct solution. First, note that long as the stability condition EZ < ET holds, the total workload (( 22) such that Eg (Xx)) Vxx) E(-r2T + Z) < holds when æ is far away from the boundary. Second, the "boundary removal technique" introduced in (Qu al. 2023) shows that the above drift can be extended the boundary as a contractive drift E,D](
+ is the most natural Lyapunov function
V(x) E(-r2T + Z) < as if the boundary (that causes anti-drift) never exists. The plane in Figure 5.2 (left) demonstrates that
DCDC has already mastered the above two steps! Again, we conclude this example with convergence bound W (X,,, Xoo) < 5.67(1 0.017)" when Xo 0.

---

Figure 2: Left: The learned solution V of KV - = for the tandem network, with maximum 3.78. Right: The estimated difference KV V. with maximum -0.0668, mean -0.0989, standard deviation 0.0097.
5.3 Discovery meaningful wedge-like Lyapunov functions
Lyapunov functions usually denoted by in the literature, and V typically represents the shape of Lyapunov functions. As mentioned in the introduction, the CDE solution is new type of Lyapunov function. In most cases, it is also V-shaped, representing the drift towards some contractive region. However, Markov chains sometimes exhibit neither drift nor contraction, such as when SGD is stuck non-strongly aon-strongly-oovvee convexx basin or when the water level of the Moran dam (Stadje [993) neither too low nor too high. Here, we use the simplest example, two-sided regulated random walk 1/3, 1/3], to illustrate that DCDC discovers
f()) = max(min(x + 1/2). 11/2) with upside-down A-shaped Lyapunov functions to address the above issue.
1.-
-000
6-
08-
94
224
24
Figure 3: Left: The learned solution of KV VV = -0.1 for the regulated random walk, with maximum 0.972. Right: The estimated difference KV V. with maximum -0.0662, mean -0.0964, standard deviation 0.0106.
In 1/6, 1/6], the chain exhibits neither drift (Z is symmetric) nor contraction (#1/2 boundaries not reachable in one step). The wedge in Figure 5.3 (left) creates an artificial drift to maintain the CD. In (Qu et al. (202)). similar function introduced
tool to study stylized non-strongly-come SGD. DCDC not only discovers this tool but also makes the wedge meaningful. As mentioned in remark below Theorem [ the CDE solution generated by DCDC represents an average space- discounted cumulative reward, where an agent collects reward within shrinking ball. Why does starting from the middle lead the highest reward? Because the ball starting there has the longest lifespan before hitting the boundary and collapsing into single point.

---

5.4 Recovery of exact convergence rates
Finally, demonstrate the potential of DCDC to accurately recover exact convergence rates, we examine a class of d-dimensional autoregressive processes
f(z) H Z, 2, 2
where random vector Z is integrable and constant matrix H is symmetric with all its eigenvalues (0, 1). The exact convergence rate of this Markov chain Wasserstein distance can be explicitly computed by pen and paper.
Proposition Let be the Markov chain defined by Xo = 0, then
0 /IH"III/V W(X, X S H Y Σ k=1
Hk-
17k-17g
where Zy 's are iid copies of Z. Let À be the largest eigenvalue of H. Then E || = ((x)) as long as Y does not concentrate on the orthogonal complement of the eigenspace associated with X.
For the autoregressive process, let d = 3 and
0.4
0.2
0.1
=
0.2
0.5
0.2
0.1
0.2
0.6/
with À 0.850. Let Z be uniformly sampled from B1 (1 n R. Note that the resulting Markov
chain cannot escape from (1) R After plugging into the simulator of (3) DCDC generates V = 0.668, which recovers the exact convergence rate
KV = - U/V)V = (1 - 0.1/0.668) = 0.850V = AV.
6 Conclusions
We introduce DCDC, a potent framework that enables the use of deep learning techniques to tackle the problem of estimating convergence stationarity of complex, general state-space Markov chains. Our approach unlocks the key to using scalable data-driven tools to tackle this important problem. In future work, we plan to use these results in the context of general state-space reinforcement learning. control of ergodic systems, and related applications by employing the CD condition as policy regularizer.
Limitations
DCDC solves CDEs compact spaces. A potential strategy to handle non-compact spaces is discussed in Section 3.2 Sample complexity lower/upper bounds are not studied in this paper and they are left for future research.
Acknowledgments and Disclosure of Funding
The material in this paper is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-20-1-00 1-0397. Additional support is gratefully acknowledged from NSF 2118199, 2229012, 2312204. and ONR 13983111.
References
Christophe Andricu, Gersende Fort, and Matti Vihola. Quantitative convergence rates for subgeomet- ric Markov chains. Journal of Applied Probability, 52(2):391-404, 2015.
Peter Baxendale. Renewal theory and computable convergence rates for geometrically ergodic Markov chains. Annals of Applied Probability, 15(1B):700-738 2005.
10

---

Oleg Butkovsky. Subgeometric rates of convergence of Markov processes in the Wasserstein metric. The Annals of Applied Probability, 24(2):526 552,, 2014.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314, 1989.
Charles Dawson, Sicun Gao, and Chuchu Fan. Safe control with learned certificates: A survey of neural Lyapunov, barrier, and contraction methods for robotics and control. JEEE Transactions on Robotics, 2023.
Randal Douc, Gersende Fort, Eric Moulines, and Philippe Soulier. Practical drift conditions for subgeometric rates of convergence. The Annals of Applied Probability, 14(3):1353-1377) 2004.
Alain Durmus and Éric Moulines. Quantitative bounds of convergence for geometrically ergodic Markov chains in the Wasserstein distance with application to the Metropolis adjusted Langevin algorithm. Statistics and Computing. 25(1))5-19, 2015.
Alain Durmus, Gersende Fort, and Éric Moulines. Subgeometric rates of convergence in Wasserstein distance for Markov chains. Annales de l'Institut Henri Poincaré, Prohabilités et Statistiques, 52 (4):1799-1822, 2016.
Alison L Gibbs. Convergence in the Wasserstein metric for Markov chain Monte Carlo algorithms with applications to image restoration. Stochastic Models, 20(4):473-4p) 2004.
Martin Hairer, Jonathan Mattingly, and Michael Scheutzow. Asymptotic coupling and a general form of Harris' theorem with applications to stochastic delay equations. Probability Theory and Related Fields, 149(1):223-259, 2011.
Stefan Heinrich and Eugène Sindambiwe. Monte Carlo complexity of parametric integration. Journal of Complexity, 1533)3177341, 1999.
Yifan Hu, Xin Chen, and Niao He. Sample complexity of sample average approximation for conditional stochastic optimization. SIAM Journal on Optimization, 30(3):2103-211 2133, 2020a.
Yifan Hu, Siqi Zhang, Xin Chen, and Niao He. Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 2759-2770. Curran Associates, Inc., 2020b.
Søren F Jarner and Gareth O Roberts. Polynomial convergence rates of Markov chains. The Annals of Applied Probability, 12(1):224-247) 2002.
Offer Kella and Ward Whitt. tandem fluid network with Lévy input. Queueing and Related Models, pages 1 112-128, 1992.
Jun Liu, Yiming Meng, Maxwell Fitzsimmons, and Ruikun Zhou. Physics-informed neural net- work Lyapunov functions: PDE characterization, learning, and verification. arXiv preprint arXiv:2312.00131, 2023.
Sean Meyn and Richard L. Tweedie. Markov Chains and Stochastic Stability. Cambridge Mathemati- cal Library. Cambridge University Press, 2 edition, 2009.
Sean Meyn, Robert L Tweedie, et al. Computable bounds for geometric convergence rates of Markov chains. The Annals of Applied Probability, 4(4):981-1011, 1994.
Chutiphon Pukdeboon. A review of fundamentals Lyapunov theory. J. Appl. Sei, 10(2):55-61, 2011.
Qian Qin and James P Hobert. On the limitations of single-step drift and minorization in Markov chain convergence analysis. The Annals of Applied Probability, 31(4):1633-165, 2021.
Qian Qin and James P. Hobert. Geometric convergence bounds for Markov chains in Wasserstein distance based on generalized drift and contraction conditions. Annales de I' l'Instiuu Henri Poincaré, Probabilités Statistiques, 58(2):872-88) 2022a.

---

Qian Qin and James P Hobert. Wasserstein based methods for convergence complexity analysis of MCMC with applications. The Annals of Applied Probability, 32(1):124-1666 2022b.
Yanlin Qu, Jose Blanchet, and Peter Glynn. Computable bounds on convergence of Markov chains in Wasserstein distance. arXiv preprini arXiv:2308. 10341, 2023.
Maziar Raissi, Paris Perdikaris, and George E Kariaaakii. Physics- Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational Physics, 378:686-707, 2019.
Jeffrey S Rosenthal. Minorization conditions and convergence rates for Markov chain Monte Carlo. Journal of the American Statistical Association, 90(430):558-566, 1995.
Justin Sirigmano and Konstantinos Spiliopoulos. DGM: A deep learning algorithm for solving partial differential equations. Journal of Computational Physics, 375:1339-1364, 2018
Wolfgang Stadje. A new look at the Moran dam. Journal of Applied Probubility, 30(2):489-495 1993.
David Steinsaltz. Locally contractive iterated function systems. Annals of Probability, pages 1952-1979, 1999.
12

---

A Appendix
Proof of Theorem
Note that
(x) kKW, U())
(f(())) +z)))
=IDX00BDDD6600M.ddcccdcl11111111 +U(z))
E
(X()))
II Df
+
Ex
U(X+) II
k=1
k=0
By
U(x DX((X--))
1=1
As + 00, have V, S W.
0o and
U( II Diit((x)))
=
80
E
Σ U(X++1) Diit
1=0
E
Σ U DIA(X)))
LK=1
1=1
= Vx) Uzx.
Let V be another solution of KV = U. Similar to W.,
n-1 U(X)) DMXX-L)
v*(x= Eg (X,) II DJ + Σ Eg A=1
k=
As - oC, we have 2 V.. V.. and hence V", is unbounded, then KV V doesn't have bounded solution. If V*, and hence V., is bounded, we claim that they are the same solution. It suffices to show that the first term on the RHS of (4 vanishes as n + co. This is true because
V.(x) <00 + E. (Xw)) II (D
+0 Ex V*(X.) II ((A((x=1) +0
n
where the last step follows from sup V < oo and inf U 0.
Proof of Theorem 2 Since continuous functions compacts sets are bounded, by Theorem V, is the unique continuous solution of KV V U. By the universal approximation theorem (C (Cybenko 1989), there exists a single-layer neural network with sigmoid activation (Vo A E θ} (é is some Euclidean space) and its realization Vo, such that [[Vo. VVllaa <c/(L + where L |EDf Then
KVV - Vo. +U KV. - V. + Ul + Vo. - V.ll + +VV. - KV
<0 (I + 1)+ Le/(L+1)
Proof of Theorem The setting introduced in Section 2 is special case the setting in QQu et 2023), allowing us to directly invoke the results from that work. In particular, X is assumed
13

---

to be convex, the intrinsic metric used in (Qu et al 2023 reduces to the Euclidean metric. From
KV < <V- U, we have
KV VV
U V - U. V sup V svV, r= inf sup V.
By Theorem 3 in Qu al.
2023).
r
Xox)
B1 - xill + -(XI - -Xo) Cr
inl
where
C E - xxXx
Xx))
inf (inf V/ sup V)
and Ú is a U0, 1] random variable independent of Xo and X1.
Proof of Theorem F The proof is similar to the proof of Theorem in (Qu et al. (023), but in our specific setting, the proof becomes much simpler notation-wise. As the proof our Theorem [ we have
V=V((x) Eg vo((.) I V=(),,
(a(
===
1=1
Following the same induction process as in (Qu et al. 2023), we have
n + m - - 1)
Vm(x) 2 Σ Cm. K Vo(r),
Cm,n
==0
Let F2 = fn .... fi and Fú = .... o fn be the n-fold forward and backward composition, respectively. Given f independent of anything else,
((x) (yddy
(x)
Cm,n
K" K"Vooy)
50
((x)
Cm,
E
Vo(Ex II DD((--
dy 1=1
Fa(S(n))
Cm, EE
Vo(z)dz
n=0
F((m)
1n)1(1)
Cm,n
E
Vo(2)dz
Pa(w)
m=0
For partieular
((0)
x
fntalle)
Vi (y) 2
Cm,n E
Volz)dz
Falz)
(a)
Cm. EE
Vo(2)dz
Fa(z)
2mn inf Vo E F((()))) - F (x)
By integrating with respect to the initial distribution Xo.
I X - X1|| (Xn + Ú(x, Xo)) 20m,a inf Vo E (a(o)) - Fox (Xo)l
2 Cm,a inf Vo WX,,,
(n + 1) ... (n 1)
in W(Xn, X
(m - 1)...
m
k +1 inf Vo
14

---

Proof of Theorem 5 find M, N such that
As X' is compact, without loss of generality, let X' = [0, 115. The main goal is
P sup NEx
sup ZEM
+C S.
This probability is bounded by the sum of
P sup (V (x (x))+ +U()]]
sup ((()) + (5)
DE
3EM
and
p sup [KV
V(x) + U(x)] sup
[xV(<)) V(x) + U(x) +
(6)
cEM
=EM
To bound
5
we need to bound the Lipschitz constant of KV V U. For x, EX
KV(=) KV(y)
(ff(=))(((z)) - I
(f) (D(() + (ED (BDf(=)IV(f(a)) - v(f(w)) + (E)
- V(f(g)
<DV.ED$ || -yy + sup V ED ||0--11 vll
where DV is the Lipschitz constant of V. Then, the Lipschitz constant of KV V + U bounded by
i, DV EDf² + sup V. ED + DV DU.
Then (5) bounded by (10, 1] & Br) where = (/2.). To bound this probability, we divide the unit cube into C = (Vd/r) = (2īvd/e) sub-cubes with edge length f/Vd. Then [0, 1] ø UseM Br implies that there exists at least one sub-cube that does not contain any element of M. This is equivalent to failing to collect different coupons within M draws. It is well-known that we need ( log C) on average to collect Ö different coupons. By Markov inequality, we can choose M = O('' log C/8) O(log(1/e)(BBee) to reduce the failure probability below 8/2.
To bound
6 let IM arg m (KV(x) ((x) Ux))..
By Chebyshev inequality,
P KV(MM) - V(aM) + U(xM) > sup
- V(()) V(+)) + +c/2l,)) (KV(EM) (((M) +((m) > KNV(EM) V(()) + +c/2
xEM
<P
=P (KV(EM) (NV(EM)+ M
Var
2/4
4 ssup V2, EDD²
Ne²
<6/2
when N 2 (8sup V2 -
Proof of Proposition
By X, = and
we have
X, H k Z and X, = Σ
H 1 7
k=1
where N, is the backward chain. By definition,
W(X,, Xx) -
Σ
1
Zk
=E H
H Z
= =E H
R=n+1
15

---

Let Lip(1) be the family of functions on R that are 1-Lipschitz with respect to the 2-norm ||-|| Let ||-II, be the 1-norm. By the Kantorovich CesbrovicccRubbstteeeen duality,
W(X,, X
sup Bh(X,o) Ex(x,)) hELip(1)
2 E X || ||xx
=E |xx - -xnll1/ /Vd
> E |xx - Xxll /Va
E HHYIII/V,
where the second line is because II-I1, / is 1-Lipschitz with respect to ||.|| the third line is because X 2 Xn 2 0, and the fourth line is because |1-11; 2 ||-I|- Let A be the diagonal matrix containing all the eigenvalues of H. Let Q be the orthogonal matrix containing the (column) eigenvectors of H. Then
H" QA"QQQQ
Σ Xaaa
Recall that is the largest eigenvalue of H. Then
E /| = E Σ (A./A)"
TV - E
Σ NE!
q:g. Ty
as n 00
where (q: : E } are the eigenvectors corresponding to A. Since Z is integrable and Y does not concentrate on the orthogonal complement of the eigenspace associated with X, the above limit is finite and positive.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All claims are justified.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have a "Limitations" section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

Justification:
All proofs are in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The paper provides enough details for reproduction, and the code provides one-click reproduction.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
18

---

Answer: [Yes]
Justification:
Code with instructions is included in the submission.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https guwdes/dde/eeee Cooeeeoodeesssseeeeee //nips.com htc/://bbb///udddd///eeeeeueisss ssiniilicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We present enough details in the paper and full details in the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report the average error and its standard deviation in the numerical experi-
ments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
19

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: As mentioned in the paper, an M2 MacBook Air suffices with 8GB RAM suffices.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httph::t////// htttt::///eurips.oooo http://wpw...............ccaaaaa
Answer: [Yes]
Justification:
Our research conforms with the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use existing assets
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
22


Reviews:
[{"review_id": "i8yaHI3OC8", "reviewer": "Reviewer_ituE", "summary": "#### Summary\nThe paper introduces the Deep Contractive Drift Calculator (DCDC), a novel sample-based algorithm for bounding the convergence rates of general state-space Markov chains to stationarity in Wasserstein distance. The method leverages deep learning to solve the Contractive Drift Equation (CDE), providing explicit convergence bounds. The paper includes theoretical analysis, sample complexity, and empirical validation on realistic Markov chains.", "questions": "#### Questions\n1. **Computational Complexity**:\n    - Could you provide more details on the computational complexity of the DCDC algorithm, particularly for high-dimensional state spaces? How does the method scale with increasing dimensions?\n\n2. **Comparison with Existing Methods**:\n    - How does the DCDC method compare empirically with existing state-of-the-art methods for bounding convergence rates of Markov chains? Are there specific scenarios where DCDC significantly outperforms these methods?\n\n3. **Generality**:\n    - The method is validated on specific types of Markov chains. Do you foresee any challenges in applying DCDC to other types of Markov chains, such as those with more complex dynamics or in higher-dimensional spaces?\n\n4. **Sample Complexity**:\n    - While you provide a theoretical analysis of sample complexity, can you offer practical guidelines or heuristics for choosing sample sizes in different applications? How sensitive is the method to the choice of sample size?\n\n5. **Practical Applications**:\n    - Can you discuss potential practical applications of the DCDC method in more detail? For instance, how might this method be applied in real-world scenarios such as reinforcement learning or stochastic optimization?\n\n6. **Assumptions and Limitations**:\n    - The paper discusses some assumptions and limitations. Could you elaborate on the key assumptions that are critical for the theoretical results, and how robust the method is to violations of these assumptions?", "limitations": "no", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "#### Strengths\n1. **Innovative Approach**: The use of deep learning to solve the Contractive Drift Equation (CDE) is novel and bridges a gap between deep learning and traditional mathematical analysis.\n2. **Theoretical Rigor**: The paper provides thorough theoretical foundations, including the derivation of the CDE and detailed proofs of convergence bounds.\n3. **Practical Implications**: The approach is validated on realistic Markov chains, demonstrating its applicability to problems in operations research and machine learning.\n4. **Clarity of Exposition**: The paper is well-written, with clear explanations of the methodology and theoretical results.", "weaknesses": "#### Weaknesses\n1. **Computational Complexity**: The approach may be computationally intensive, particularly for high-dimensional state spaces. More discussion on computational efficiency and scalability would be beneficial.\n2. **Comparison with Existing Methods**: While the paper discusses theoretical advantages, empirical comparisons with existing state-of-the-art methods for convergence analysis are limited.\n3. **Generality**: The method is demonstrated on specific types of Markov chains. Extending the empirical validation to a broader range of applications would strengthen the paper.\n4. **Sample Complexity**: Although the sample complexity is analyzed, practical guidelines for choosing sample sizes in different scenarios would enhance the utility of the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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).\n\n1&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.\n\n2 *Comparison with Existing Methods*:\nWe 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].\n\n3 *Generality*: \nMarkov 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.\n\n5 *Practical Applications*:\nThanks 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\n\n6 *Assumptions and Limitations*: \nThe 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.\n\n[1] Ergen, T., Pilanci, M., “Global optimality beyond two layers: Training deep ReLU networks via convex programs”, 2021\n\n[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\n\n[3] Lu, Y., Blanchet, J., Ying, L., “Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent”, 2021\n\n[4] Qu, Y., Blanchet, J., Glynn, P., “Computable bounds on Convergence of Markov chains in Wasserstein distance”, 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A3o2IE3pa3", "reviewer": "Reviewer_wP6n", "summary": "The paper studies the problem of convergence rate analysis for general state-space Markov chains. They propose Deep Contractive Drift Calculator (DCDC), the first general-purpose sample-based algorithm for bounding the convergence of Markov chains. There are two components, a theoretical one that utilize an auxiliary function (a solution of a certain equation) to bound convergence, and an empirical one that utilize deep neural networks to approximate the auxiliary function. Furthermore, the authors provide statistical guarantees on the approximation.", "questions": "No.", "limitations": "I'm not seeing any limitations of essence not addressed in this paper.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Extremely well written paper. The abstract gives a quite clear overview of the paper, pointing out the main contribution in this paper and the importance of the problem addressed without exaggeration. The wording in the paper is succinct, subjective, yet pleasant to read. I'm not an expert in the field but I quickly understand the importance of the paper. It appears to me that the whole presentation is rather mature and professional.\n2. The authors study a problem of fundamental importance and give a general solution that is simple yet effective and without sound guarantees. The authors borrow the idea of Lyapunov function approximated by neural networks and successfully apply it to the convergence problem of Markov chains, which in my opinions is of some fundamental importance. Furthermore, the authors provide statistical guarantees on the approximation, forming a rather complete story.", "weaknesses": "I'm not able to find effective weaknesses in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your positive feedback. Please feel free to read the other rebuttals.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tcPyPTrVC4", "reviewer": "Reviewer_3Pb4", "summary": "The authors proposed a novel computational method to estimate the convergence rate of general Markov Chains. They utilized neural network to verify if contration drift (CD) holds for a given Markov Chain. As an extension to a prior work [1], the authors provided further theoretical analysis of their methods, and proposed an explicit formula of the convergence rate. Various numerical experiments were conducted to justify the applicability.", "questions": "1. What is the relationship between CD and conventional inequailities such as Poincare inequality, Log Sobolev inequality?\n\n1. I wonder the choices of $U$. In all the experiments, $U$ is fixed as a constant. How is this constant selected? Also, is there any other choice of $U$ that can be considered in practice? How does different choices of $U$ lead to different convergence rate estimation? What is the practicability of sequentially learning neural network in section 3.4?\n\n2. The convergence rate in Theorem 3 depends on $\\inf/\\sup V$. How is inf/sup $V_\\theta$ computed in practice?\n\n3. Does there always exist $U,V$ to satisfy CD? If not, how can one know that from DCDC? In another word, how can one tell the failure of training of network from the fact that CD doesn't hold?", "limitations": "The limitations are pointed out in the weakness and question part.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. I'm not familiar with the topic about estimating the convergence rate of a given Markov chain. In general, the idea is very novel to me. Since this problem is very difficult, it seems that the proposed method is indeed promising.\n\n2. The paper provides detailed theoretical analysis, including the explicit formula of convergence rate and sample complexity.", "weaknesses": "1. The paper is somewhat intricate and difficult follow. I notice that it is built upon [1], but more detailed background and related work should be provided to improve readability. Specifically, the authors should discuss more previous methods if there exist and make comparisons theoretically or numemrically. \n\n2. In experiments, the authors only showed the results of their algorithms. I think the convergence rate should be verifed through directly simulating the Markov chain and computing Wasserstein distance between the sampled distribution and stationary distribution.\n\n3. The authors only conducted experiments in 2D, lacking high dimensional examples.\n\n4. A more fundamental problem is that how to verify whether CD holds in practice in high dimensional case. The inequality is defined in the pointwise sense, which is difficult to verify due to the curse of dimensionality.\n\n[1] Qu, Yanlin, Jose Blanchet, and Peter Glynn. \"Computable Bounds on Convergence of Markov Chains in Wasserstein Distance.\" arXiv preprint arXiv:2308.10341 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your detailed feedback. In the following, we address the concerns (W1-4) and answer the questions (Q1-4).\n\nW1. 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.\n\nSince 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.\n\nW2. 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.\nNow 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).\n\nW3. 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).\n\nW4. 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.\n\nQ1. 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).\n\nQ2. 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.\n\nWhen $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.\n\nQ3. 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]).\n\nQ4. 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. \n\n\n[1] Qu, Y., Blanchet, J., Glynn, P., “Computable bounds on Convergence of Markov chains in Wasserstein distance”, 2023\n \n[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\n\n[3] Douc, R., Moulines, E., Priouret, P., Soulier, P., “Markov Chains”, 2018\n\n[4] Scaman, K., Virmaux, A., “Lipschitz regularity of deep neural networks: analysis and efficient estimation”, 2018\n\n[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\n\n[6] Lu, Y., Blanchet, J., Ying, L., “Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent”, 2021", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
* We appreciate the feedback and comments of all of the referees. We note that two out of the three reports rate the paper with an evaluation of 8 (strong accept) whereas one of the referees has some concerns providing an evaluation of 4 (borderline reject). 
* We try to focus most of the response below to answer questions raised and to address concerns raised. The main issues have to do with the existence of a solution to the CD, the answer is yes, but it may diverge and this could be practically detected in training. The second issue has to do with complexity results and the fact that learning a function in high dimensions is subject to the curse of dimensionality. But this issue is present in every single application of deep learning, which in the end involves approximating high dimensional functions based on a limited sample.
* The bottom line is that this paper is the first one that enables the use of deep learning to estimate rates of convergence to stationarity for Markov chains that take values on a general state space. We acknowledge the limitations and we’ll be happy to add more discussion (along the lines of what we include in this report, taking as a template the literature on solutions to PDEs based on deep learning techniques).

Meta-review: This paper proposes a general-purpose deep learning-based algorithm to compute the convergence rate of Markov chains to their stationary distribution. The proposed method consists of two components:

1. **Theoretical Tool:**  
   The first component is a theoretical tool that demonstrates how the convergence rate of the Markov chain can be exactly determined by solving a Contractive Drift Equation (CDE), derived from the contractive drift condition of the Markov chain.

2. **Network-Based Solver:**  
   The second component is a network-based solver for the CDE equation. The authors provide examples on Stochastic Gradient Descent (SGD) and other practical Markov chains to showcase how the convergence rate can be obtained for complex, real-world chains.

All reviewers agree that this work is well-written and presents a novel solution that bridges the gap between the theoretical analysis of Markov chains and data-driven algorithms. As suggested by the reviewers, it would be beneficial to include refined experiments that verify the convergence rate by running sufficient steps of the Markov chains.

Overall, this paper is a clear acceptance, and the idea of using deep learning to estimate the convergence of Markov chains deserves more attention from the community.
Decision: Accept (spotlight)