修士論文 要旨

Convergence Rate Analysis of Markov Chain Monte Carlo
Based on Coarse Ricci Curvature and Its Improved Variant
数理情報学専攻 48-226201
指導教員

1 Introduction
The quantiﬁcation of convergence rates of MCMC isSho Adachi (足立 勝)
Professor Fumiyasu Komaki （駒木 文保 教授）
on R. Then, the following holds:∫ ∫ 𝑥d(𝜈1 − 𝜈2 ) d𝑥.
𝑊1 (𝜈1 , 𝜈2 ) =R

a critical issue. There are two principal metrics in thisliterature: the total variation distance and the Wasser-−∞This property of 1-Wasserstein distance plays signiﬁcantly important role in this thesis.

stein distance. While the convergence rate in the total

As previously noted, the coarse Ricci curvature pro-variation distance has been intensively studied (e.g., [2]),posed by [1] can quantify the convergence rate w.r.t. 𝑊1 .

there is much room for developing the convergence rate

Its deﬁnition is as follows.

analysis in the Wasserstein distance, particularly for theMetropolis-Hastings algorithm, which is one of the mostDeﬁnition 2.3. Let 𝑥, 𝑦 ∈ X be two distinct points. Thewidely used classes of MCMC including random-walkcoarse Ricci curvature of a transition kernel {𝑚 𝑥 } 𝑥 ∈X

Metropolis (RWM), Gibbs sampler, Metropolis Adjusted

along (𝑥𝑦), 𝜅(𝑥, 𝑦), is deﬁned as

Langevin Algorithm (MALA), and Hamiltonian Monte𝜅(𝑥, 𝑦) := 1 −Carlo (HMC).

𝑊1 (𝑚 𝑥 , 𝑚 𝑦 ).
𝑑 (𝑥, 𝑦)In this thesis, we consider target distributions deﬁned

The coarse Ricci curvature is related to the convergenceon R and analyze the convergence rates of various MCMC

rate as the following proposition states (See [1, Corollaryalgorithms (mainly Metropolis-Hastings) in 1-Wasserstein21] for its proof):

distance by proposing a new quantity. The proposal canProposition 2.4. For a transition kernel {𝑚 𝑥 } 𝑥 ∈X , if

be understood as an improved variant of the coarse Ricci
curvature, which is a representative quantity for deriving
convergence rates in the Wasserstein distance [1].

𝜅 := inf ( 𝑥,𝑦) ∈X ×X 𝜅(𝑥, 𝑦) > 0 holds, then {𝑚 𝑥 } 𝑥 ∈X has aunique stationary distribution. Moreover, the convergence
rate of {𝑚 𝑥 } 𝑥 ∈X is 𝑂 ((1 − 𝜅) 𝑛 ) for any initial distribution.

2 Preliminaries
We let (X , 𝑑) denote a Polish space and B(X ) be theBorel 𝜎-algebra over X . We ﬁrst state the deﬁnition of3

The proposed variant
Let {𝑚 𝑥 } 𝑥 ∈R be the transition kernel of a Markov

the 1-Wasserstein distance.

chain on R.

Deﬁnition 2.1. For probability distributions 𝜈1 and 𝜈2 ondenote the cumulative distribution function of 𝑚 𝑥 , i.e.,∫𝑧
𝐹𝑥 (𝑧) := −∞ 𝑚 𝑥 (𝑠)d𝑠 for 𝑧 ∈ R. We introduce the follow-

X , the 1-Wasserstein distance between them, 𝑊1 (𝜈1 , 𝜈2 ),is deﬁned as∫
𝑊1 (𝜈1 , 𝜈2 ) :=inf𝜉 ∈Π(𝜈1 .𝜈2 )( 𝑥,𝑦) ∈X ×X𝑑 (𝑥, 𝑦)𝜉 (d𝑥, d𝑦),In addition, for each 𝑥 ∈ R, we let 𝐹𝑥

ing quantity for Markov chains on R:∫ ∞𝜕𝐹𝑥
𝑊 (𝑥) :=(𝑧) d𝑧
−∞ 𝜕𝑥

(1)

This is the proposed variant of the coarse Ricci curvature.

where Π(𝜈1 , 𝜈2 ) denotes the set of couplings of 𝜈1 and 𝜈2 .

The following theorem asserts that if sup 𝑥 ∈R 𝑊 (𝑥) < 1,In the special case where X = R and 𝑑 is the Euclidean

then sup 𝑥 ∈R 𝑊 (𝑥) directly determines the convergence rate

distance, we can express the distance explicitly using cu-of the Markov chain.

mulative distribution functions.

Theorem 3.1. Suppose that 𝐹𝑥 (𝑧) is diﬀerentiable w.r.t.

Theorem 2.2. Let 𝜈1 and 𝜈2 be probability distributions

𝑥 for each 𝑧. In addition, assume that lim 𝑦→∞ 𝐹𝑦 (𝑧) is aconstant which is independent of 𝑧. If 𝜔 := sup 𝑥 ∈R 𝑊 (𝑥) <Convergence Rate Analysis of Markov Chain Monte CarloBased on Coarse Ricci Curvature and Its Improved Variant (Sho Adachi (足立 勝))

1, then the convergence rate of the Markov chain with

As a result, we can not apply Proposition 2.4.

respect to 1-Wasserstein distance is given by 𝑂 (𝜔 𝑛 ).
Next, we state a result which relates our proposed quantity 𝑊 (𝑥) to the coarse Ricci curvature.
Theorem 3.2. If there exists some 𝑔 𝑥 : R → R such that∫𝑥 (𝑧) |
𝑔 (𝑧)d𝑧 < ∞ and |𝐹𝑥+𝜖 (𝑧)−𝐹≤ 𝑔 𝑥 (𝑧) for all 𝑧 ∈ R,𝜖R 𝑥then lim 𝜖 →0 (1 − 𝜅(𝑥, 𝑥 + 𝜖)) = 𝑊 (𝑥) holds.

Under the assumption in Theorem 3.2, sup 𝑥 ∈R 𝑊 (𝑥) ≤1 − inf ( 𝑥,𝑦) ∈R2 𝜅(𝑥, 𝑦) holds, and thus the proposal is en-

図 2. plot of 1 − 𝜅(𝑥, −𝑥)

sured to derive tighter convergence rates than the coarse
Ricci curvature.
4.2Example 2. (MALA and HMC)

4 Examples of the proposed quantity

We deﬁne the target distribution 𝜋 as 𝜋 = N (0, 1).

MetIn HMC, two parameters are necessary for discretizing

As notation, we let 𝑊 (𝑥) denote the proposed quantityof a Markov chain with the Metropolis test.
4.1 Example 1. (random walk Metropolis)

We give an example where the proposed quantity (1) can
derive a convergence rate of the random walk Metropolis(RWM) while the coarse Ricci curvature fails. We deﬁne
the target distribution 𝜋 as N (0, 𝜎 ∗ 2 ) and set the proposal
distribution as 𝑚 𝑥 = N (𝑥, 𝜎 2 ). In addition, we put anassumption that 𝜎 < 𝜎 ∗ , which facilitates our analysis ofHamilton’s equation by LeapFrog integration: the time
step width 𝜖 and the number of LeapFrog integrations 𝑁.
Figure 3 compares values of the proposed quantity among
HMC with diﬀerent 𝑁 (Here, 𝜖 𝑁 is ﬁxed). We highlightthat HMC with 𝑁 = 1 is equivalent to MALA. Figure 3
shows that HMC attains faster convergence than MALA
Met

since sup 𝑥 𝑊 (𝑥) of HMC (𝑁 > 1) is smaller than that ofMALA (𝑁 = 1).

the quantity (1).
Met

4.1.1 Analysis of 𝜔 := sup 𝑥 ∈R 𝑊 (𝑥)Met

In this example, we can evaluate 𝑊 (𝑥) analytically andFigure 1 is its plot. The fact 𝜔 < 1 and Theorem 3.1

Met

図 3. comparison of 𝑊 (𝑥) of HMC with diﬀerent 𝑁

Other examples and the extension of the proposed quantity from R to other sample spaces will be discussed in theMet

図 1. plot of 𝑊 (𝑥) (𝑥 > 0)

presentation.

参考文献
indicates that RWM achieves the exponential convergence.
4.1.2 Analysis of the coarse Ricci curvature

For the coarse Ricci curvature, we can prove
lim 𝑥→∞ (1 − 𝜅(𝑥, −𝑥)) = 0. As Figure 2 indicates, thisfact can be conﬁrmed through numerical experiments too.

[1] Y. Ollivier, Ricci curvature of Markov chains on metricspaces, Journal of Functional Analysis, 256(3), pp. 810–864, 2009.
[2] J. S. Rosenthal, Minorization conditions and convergence
rates for Markov chain Monte Carlo, Journal of the American Statistical Association, 90, pp. 558–566, 1995.