# On the convergence of an improved discrete simulated annealing via landscape
modification

Michael C.H. Choi  School of Data Science, The Chinese University of Hong
Kong, Shenzhen and Shenzhen Institute of Artificial Intelligence and Robotics
for Society, Guangdong, 518172, P.R. China<EMAIL_ADDRESS>
###### Abstract.

In this paper, we propose new Metropolis-Hastings and simulated annealing
algorithms on finite state space via modifying the energy landscape. The core
idea of landscape modification relies on introducing a parameter $c$, in which
the landscape is modified once the algorithm is above this threshold
parameter. We illustrate the power and benefits of landscape modification by
investigating its effect on the classical Curie-Weiss model with Glauber
dynamics and external magnetic field in the subcritical regime. This leads to
a landscape-modified mean-field equation, and with appropriate choice of $c$
the free energy landscape can be transformed from a double-well into a single-
well, while the location of the global minimum is preserved on the convexified
landscape. Consequently, running algorithms on the modified landscape can
improve the convergence to the ground-state in the Curie-Weiss model. In the
setting of simulated annealing, we demonstrate that landscape modification can
yield improved mean tunneling time between global minima, and give convergence
guarantee using an improved logarithmic cooling schedule with reduced critical
height. Finally, we discuss connections between landscape modification and
other acceleration techniques such as Catoni’s energy transformation
algorithm, preconditioning, importance sampling and quantum annealing.

AMS 2010 subject classifications: 60J27, 60J28

Keywords: Metropolis-Hastings; simulated annealing; spectral gap; Curie-Weiss;
metastability; landscape modification; energy transformation; convexification

###### Contents

  1. 1 Introduction
    1. 1.1 Notations
  2. 2 Metropolis-Hastings with landscape modification
    1. 2.1 Linear $f$: Metropolis-Hastings with logarithmic Hamiltonian and Catoni’s energy transformation method
    2. 2.2 Quadratic $f$: Metropolis-Hastings with $\arctan$ Hamiltonian
    3. 2.3 Square root $f$: Metropolis-Hastings with sum of square root and logarithmic Hamiltonian
    4. 2.4 A Metropolised Ehrenfest urn with landscape modification
  3. 3 The Curie-Weiss model with landscape modification
    1. 3.1 Main results
    2. 3.2 Proof of Theorem 3.1
    3. 3.3 Extension to the random field Curie-Weiss
  4. 4 Discrete simulated annealing with landscape modification
    1. 4.1 Proof of Theorem 4.1
    2. 4.2 Proof of Corollary 4.1
    3. 4.3 Proof of Lemma 4.1
    4. 4.4 Proof of Theorem 4.2
  5. 5 Connections between landscape modification and …
    1. 5.1 Catoni’s energy transformation algorithm
    2. 5.2 preconditioning of the Hamiltonian
    3. 5.3 importance sampling
    4. 5.4 quantum annealing

##  1\. Introduction

This paper can be considered as a sequel to an earlier work by the author Choi
(2020). The original motivation is from Fang et al. (1997), who propose a
variant of overdamped Langevin diffusion with state-dependent diffusion
coefficient. In Choi (2020), we cast this idea of state-dependent noise via
landscape modification in the setting of kinetic simulated annealing and
develop an improved kinetic simulated annealing algorithm with convergence
guarantee. In this paper, we apply the idea of landscape modification to the
finite state space setting in Metropolis-Hastings (MH) and simulated
annealing, and investigate the benefits and speedups that this technique can
bring in particular to the analysis of Curie-Weiss (CW) model and stochastic
optimization.

In Section 2, we begin our paper by first defining a new MH algorithm using a
modified Hamiltonian function. The modification or the transformation is based
on the introduction of two parameters, namely $f$ and $c$, which increases the
acceptance-rejection probability whenever the algorithm is above the threshold
$c$. The corresponding acceptance-rejection probability in the modified MH in
general has an integral form, but we show that this integral can be readily
calculated upon specializing into various choices of $f$ such as linear,
quadratic or square root $f$. We wrap up this section by detailing an example
on using landscape modification in the Ehrenfest urn with a linear
Hamiltonian, where we prove an upper bound on the spectral gap with polynomial
dependence on the dimension, whereas the same technique yields an exponential
dependence on the dimension for the classical MH.

In Section 3, we investigate the effect of landscape modification on the CW
model. We first consider the CW model under a fixed external magnetic field in
the subcritical regime, where the free energy landscape, as a function of the
magnetization, has two local minima. Using a Glauber dynamics with landscape
modification, we introduce a new mean-field equation, and with appropriate
choice of $c$, the free energy landscape is transformed from a double-well
into a single-well while preserving the location of the global minimum on the
convexified landscape. As a result running algorithms on the modified
landscape can accelerate the convergence towards the ground-state. We prove a
subexponential mean tunneling time in such setting and discuss related
metastability results. Similar results are then extended to the random field
CW model.

In Section 4, we consider the simulated annealing setting by driving the
temperature down to zero. We define a clipped critical height $c^{*}$ (that
depends on the threshold parameter $c$) associated with the landscape modified
simulated annealing, and prove tight spectral gap asymptotics based on this
quantity. Consequently, this leads to similar asymptotic results concerning
the total variation mixing time and the mean tunneling time in the low-
temperature regime. Utilizing existing results concerning simulated annealing
with time-dependent target function, we prove convergence guarantee of the
landscape modified simulated annealing on finite state space with an improved
logarithmic cooling schedule.

In the final section of the paper, Section 5, we elaborate on the similarities
and differences between landscape modification and other acceleration
techniques in Markov chain Monte Carlo literature such as Catoni’s energy
transformation algorithm Catoni (1996, 1998), preconditioning of the
Hamiltonian, importance sampling and quantum annealing.

###  1.1. Notations

Throughout this paper, we adapt the following notations. For
$x,y\in\mathbb{R}$, we write $x_{+}=\max\\{x,0\\}$ to denote the non-negative
part of $x$, and $x\wedge y=\min\\{x,y\\}$. For two functions
$g_{1},g_{2}:\mathbb{R}\to\mathbb{R}$, we say that $g_{1}=\mathcal{O}(g_{2})$
if there exists a constant $C>0$ such that for sufficiently large $x$, we have
$|g_{1}(x)|\leqslant Cg_{2}(x)$. We write $g_{1}=o(g_{2})$ if
$\lim_{x\to\infty}g_{1}(x)/g_{2}(x)=0$, and denote $g_{1}\sim g_{2}$ if
$\lim_{x\to\infty}g_{1}(x)/g_{2}(x)=1$. We say that $g_{1}(x)$ is a
subexponential function if $\lim_{x\to\infty}\frac{1}{x}g_{1}(x)=0$.

##  2\. Metropolis-Hastings with landscape modification

Let $\mathcal{X}$ be a finite state space under consideration,
$Q=(Q(x,y))_{x,y\in\mathcal{X}}$ be the transition matrix of a reversible
proposal chain with respect to the probability measure
$\mu=(\mu(x))_{x\in\mathcal{X}}$, and $\mathcal{H}:\mathcal{X}\to\mathbb{R}$
be the target Hamiltonian function. Denote by
$M^{0}=(M^{0}(x,y))_{x,y\in\mathcal{X}}$ to be the infinitesimal generator of
the continuized classical Metropolis-Hastings chain
$X^{0}=(X^{0}(t))_{t\geqslant 0}$, with proposal chain $Q$ and target
distribution being the Gibbs distribution $\pi^{0}(x)\propto
e^{-\beta\mathcal{H}(x)}\mu(x)$ at inverse temperature $\beta>0$. Recall that
its dynamics is given by

$M^{0}(x,y)=M^{0}_{\epsilon}(Q,\pi^{0})(x,y):=\begin{cases}Q(x,y)\min\left\\{1,e^{\beta(\mathcal{H}(x)-\mathcal{H}(y))}\right\\}=Q(x,y)e^{-\beta(\mathcal{H}(y)-\mathcal{H}(x))_{+}},&\mbox{if
}x\neq y;\\\ -\sum_{z:z\neq x}M^{0}(x,z),&\mbox{if }x=y.\end{cases}$

We shall explain the upper script of $0$ in both $M^{0}$ and $\pi^{0}$ in
Definition 2.1 below.

Let us denote the ground-state energy level or the global minimum value of
$\mathcal{H}$ to be $\mathcal{H}_{min}:=\min_{x\in\mathcal{X}}\mathcal{H}(x)$.
Instead of targeting directly the Hamiltonian $\mathcal{H}$ in the Gibbs
distribution, we instead target the following modified or transformed function
$\mathcal{H}_{\epsilon,c}^{f}$ at temperature $\epsilon=1/\beta$:

(2.1)
$\displaystyle\mathcal{H}_{\epsilon}(x)=\mathcal{H}^{f}_{\epsilon,c}(x):=\int_{\mathcal{H}_{min}}^{\mathcal{H}(x)}\dfrac{1}{f((u-c)_{+})+\epsilon}\,du,$

where the function $f$ and the parameter $c$ are chosen to satisfy the
following assumptions:

######  Assumption 2.1.

  1. (1)

The function $f:\mathbb{R}^{+}\to\mathbb{R}^{+}$ is differentiable, non-
negative and non-decreasing. Furthermore, $f$ satisfies

$f(0)=f^{\prime}(0)=0.$

  2. (2)

The parameter $c$ is picked so that $c\geqslant\mathcal{H}_{min}$.

While it is impossible to calculate $\mathcal{H}_{\epsilon,c}^{f}$ without
knowing $\mathcal{H}_{min}$ a priori, in Metropolis-Hastings what matters is
the difference of the energy function, for $x,y\in\mathcal{X}$,

$\mathcal{H}_{\epsilon,c}^{f}(y)-\mathcal{H}_{\epsilon,c}^{f}(x)=\int_{\mathcal{H}(x)}^{\mathcal{H}(y)}\dfrac{1}{f((u-c)_{+})+\epsilon}\,du.$

In the special case when we choose $f=0$, the above equation reduces to
$\mathcal{H}_{\epsilon,c}^{0}(y)-\mathcal{H}_{\epsilon,c}^{0}(x)=\beta(\mathcal{H}(y)-\mathcal{H}(x))$.
On the other hand, in the case where $c<\mathcal{H}(x)<\mathcal{H}(y)$ and $f$
is chosen such that $f(x)>0$ whenever $x>0$, then we have

$\mathcal{H}_{\epsilon,c}^{f}(y)-\mathcal{H}_{\epsilon,c}^{f}(x)\leqslant\dfrac{1}{f(\mathcal{H}(x)-c)+\epsilon}(\mathcal{H}(y)-\mathcal{H}(x))<\beta(\mathcal{H}(y)-\mathcal{H}(x)).$

Since $f$ is assumed to be non-decreasing in Assumption 2.1, the greater the
difference between $\mathcal{H}(x)$ and $c$, the smaller the upper bound in
the first inequality in the above equation, the smaller it is we would expect
for $\mathcal{H}_{\epsilon,c}^{f}(y)-\mathcal{H}_{\epsilon,c}^{f}(x)$, the
higher the transition rate
$Q(x,y)\exp\\{-(\mathcal{H}_{\epsilon,c}^{f}(y)-\mathcal{H}_{\epsilon,c}^{f}(x))\\}$,
and the landscape is modified in this sense. With these ideas and notations in
mind, we are now ready to introduce the Metropolis-Hastings chain with
landscape modification:

######  Definition 2.1 (Metropolis-Hastings with landscape modification).

Let $\mathcal{H}$ be the target Hamiltonian function, and
$\mathcal{H}_{\epsilon,c}^{f}$ be the landscape-modified function at
temperature $\epsilon=1/\beta$ introduced in (2.1), where $f$ and $c$ satisfy
Assumption 2.1. The continuized Metropolis-Hastings chain with landscape
modification $X^{f}_{\epsilon,c}=(X^{f}_{\epsilon,c}(t))_{t\geqslant 0}$ has
target distribution $\pi^{f}(x)=\pi^{f}_{\epsilon,c}(x)\propto
e^{-\mathcal{H}_{\epsilon,c}^{f}(x)}\mu(x)$, proposal chain $Q$, and its
infinitesimal generator $M^{f}=(M^{f}(x,y))_{x,y\in\mathcal{X}}$ is given by

$M^{f}(x,y)=M_{\epsilon,c}^{f}(Q,\pi^{f})(x,y):=\begin{cases}Q(x,y)e^{-(\mathcal{H}_{\epsilon,c}^{f}(y)-\mathcal{H}_{\epsilon,c}^{f}(x))_{+}}\,&\mbox{if
}x\neq y;\\\ -\sum_{z:z\neq x}M^{f}(x,z),&\mbox{if }x=y.\end{cases}$

Note that when $f=0$, the above dynamics reduce to the classical Metropolis-
Hastings $X^{0}$.

We now fix a few notations and recall some important concepts and results that
will be used in the upcoming sections, such as the spectral gap and the
critical height. We endow the Hilbert space $\ell^{2}(\pi^{f}_{\epsilon,c})$
with the usual inner product weighted by the invariant measure
$\pi^{f}_{\epsilon,c}$: for $g_{1},g_{2}\in\ell^{2}(\pi^{f}_{\epsilon,c})$,

$\langle
g_{1},g_{2}\rangle_{\pi^{f}_{\epsilon,c}}:=\sum_{x\in\mathcal{X}}g_{1}(x)g_{2}(x)\pi^{f}_{\epsilon,c}(x),$

and for $p>1$ we denote the $\ell^{p}$ norm by
$\left\lVert\cdot\right\rVert_{\ell^{p}(\pi^{f}_{\epsilon,c})}$. We write
$\lambda_{2}(-M^{f}_{\epsilon,c})$ to be the spectral gap of
$M^{f}_{\epsilon,c}$, that is,

(2.2)
$\displaystyle\lambda_{2}(-M^{f}_{\epsilon,c}):=\inf_{l\in\ell^{2}(\pi^{f}_{\epsilon,c}):\pi^{f}_{\epsilon,c}(l)=0}\dfrac{\langle-M^{f}_{\epsilon,c}l,l\rangle_{\pi^{f}_{\epsilon,c}}}{\langle
l,l\rangle_{\pi^{f}_{\epsilon,c}}}.$

Analogously, we write $\lambda_{2}(-M^{0}_{\epsilon})$ to denote the spectral
gap of $M^{0}_{\epsilon}$.

In the upcoming sections, we shall investigate and compare the total variation
mixing time between Metropolis-Hastings chain with and without landscape
modification. For any probability measure $\nu_{1},\nu_{2}$ with support on
$\mathcal{X}$, the total variation distance between $\nu_{1}$ and $\nu_{2}$ is

$||\nu_{1}-\nu_{2}||_{TV}:=\sup_{A\subset\mathcal{X}}|\nu_{1}(A)-\nu_{2}(A)|=\dfrac{1}{2}\sum_{x\in\mathcal{X}}|\nu_{1}(x)-\nu_{2}(x)|.$

The worst-case total variation mixing time is defined to be

$t_{mix}(M^{f}_{\epsilon,c},1/4):=\inf\left\\{t;~{}\sup_{x}||P_{t}^{f}(x,\cdot)-\pi^{f}_{\epsilon,c}||_{TV}<1/4\right\\},$

where $(P_{t}^{f}=e^{M^{f}_{\epsilon,c}t})_{t\geqslant 0}$ is the transition
semigroup of $X^{f}_{\epsilon,c}$.

Apart from mixing time, we will also be interested in various hitting times of
the Metropolis-Hastings chain. These variables naturally appear when we
discuss metastability results in the Curie-Weiss model in Section 3 or in
discrete simulated annealing in Section 4. For any $A\subset\mathcal{X}$, we
denote $\tau^{f}_{A}:=\inf\\{t\geqslant 0;X^{f}_{\epsilon,c}(t)\in A\\}$ and
the usual convention that $\inf\emptyset=\infty$ applies. Similarly we define
$\tau^{0}_{A}$ to be the first hitting time of the set $A$ for the Metropolis-
Hastings chain $X^{0}$. When $A=\\{x\\}$, we shall simply write
$\tau^{f}_{x}=\tau^{f}_{\\{x\\}}$ (resp. $\tau^{0}_{x}=\tau^{0}_{\\{x\\}}$).

To bound the spectral gap, we recall the concept of critical height. A path
from $x$ to $y$ is any sequence of points starting from
$x_{0}=x,x_{1},x_{2},\ldots,x_{n}=y$ such that $Q(x_{i-1},x_{i})>0$ for
$i=1,2,\ldots,n$. For any $x\neq y$, such path exists as the proposal chain
$Q$ is irreducible. We write $\chi^{x,y}$ to be the set of paths from $x$ to
$y$, and elements of $\chi^{x,y}$ are denoted by
$\gamma=(\gamma_{i})_{i=0}^{n}$. The highest value of the Hamiltonian function
$\mathcal{H}^{f}_{\epsilon,c}$ along a path $\gamma\in\chi^{x,y}$, known as
the elevation, is defined to be

$\mathrm{Elev}^{f}_{\epsilon,c}(\gamma):=\max\\{\mathcal{H}^{f}_{\epsilon,c}(\gamma_{i});~{}\gamma_{i}\in\gamma\\},$

and the lowest possible highest elevation along path(s) from $x$ to $y$ is

$G^{f}_{\epsilon,c}(x,y):=\min\\{\mathrm{Elev}^{f}_{\epsilon,c}(\gamma);~{}\gamma\in\chi^{x,y}\\}.$

Analogously, we write

$\displaystyle\mathrm{Elev}^{0}(\gamma)$
$\displaystyle=\max\\{\mathcal{H}(\gamma_{i});~{}\gamma_{i}\in\gamma\\},$
(2.3) $\displaystyle G^{0}(x,y)$
$\displaystyle=\min\\{\mathrm{Elev}(\gamma);~{}\gamma\in\chi^{x,y}\\}.$

For $M^{f}_{\epsilon,c}$, the associated critical height is defined to be

(2.4) $\displaystyle H^{f}_{\epsilon,c}$
$\displaystyle:=\max_{x,y\in\mathcal{X}}\\{G^{f}_{\epsilon,c}(x,y)-\mathcal{H}^{f}_{\epsilon,c}(x)-\mathcal{H}^{f}_{\epsilon,c}(y)\\}.$

Similarly, for $M^{0}_{\epsilon}$ its critical height is

(2.5) $\displaystyle H^{0}$
$\displaystyle:=\max_{x,y\in\mathcal{X}}\\{G^{0}(x,y)-\mathcal{H}(x)-\mathcal{H}(y)+\min_{x\in\mathcal{X}}\mathcal{H}(x)\\}.$

To simulate $X^{f}_{\epsilon,c}$ practically, we would need to evaluate the
acceptance-rejection probability, which amounts to the following integration:

(2.6)
$\displaystyle\exp\left(-(\mathcal{H}_{\epsilon,c}^{f}(y)-\mathcal{H}_{\epsilon,c}^{f}(x))_{+}\right)$
$\displaystyle=\begin{cases}1,&\mbox{if
}\mathcal{H}(y)\leqslant\mathcal{H}(x);\\\
\exp\left(-\beta(\mathcal{H}(y)-\mathcal{H}(x))\right),&\mbox{if
}c\geqslant\mathcal{H}(y)>\mathcal{H}(x);\\\
\exp\left(-\beta(c-\mathcal{H}(x))-\int_{c}^{\mathcal{H}(y)}\frac{1}{f(u-c)+\epsilon}\,du\right),&\mbox{if
}\mathcal{H}(y)>c\geqslant\mathcal{H}(x);\\\
\exp\left(-\int_{\mathcal{H}(x)}^{\mathcal{H}(y)}\frac{1}{f(u-c)+\epsilon}\,du\right),&\mbox{if
}\mathcal{H}(y)>\mathcal{H}(x)>c.\end{cases}$

In the following three subsections, we evaluate the above integrals (2.6)
where we choose $f$ to be linear, quadratic or cubic function respectively.

###  2.1. Linear $f$: Metropolis-Hastings with logarithmic Hamiltonian and
Catoni’s energy transformation method

In this subsection, we specialize into $f(u)=u$. It turns out we can
understand the landscape modification as if the Hamiltonian is on a
logarithmic scale whenever $\mathcal{H}(x)>c$.

For $x,y\in\\{\mathcal{H}(y)>\mathcal{H}(x)\geqslant c\\}$, since

$\int_{\mathcal{H}(x)}^{\mathcal{H}(y)}\frac{1}{u-c+\epsilon}\,du=\ln\left(\dfrac{\mathcal{H}(y)-c+\epsilon}{\mathcal{H}(x)-c+\epsilon}\right),$

putting the expression back into (2.6) gives

$\displaystyle\exp\left(-(\mathcal{H}_{\epsilon,c}^{f}(y)-\mathcal{H}_{\epsilon,c}^{f}(x))_{+}\right)$
$\displaystyle=\begin{cases}1,&\mbox{if
}\mathcal{H}(y)\leqslant\mathcal{H}(x);\\\
\exp\left(-\beta(\mathcal{H}(y)-\mathcal{H}(x))\right),&\mbox{if
}c\geqslant\mathcal{H}(y)>\mathcal{H}(x);\\\
\exp\left(-\beta(c-\mathcal{H}(x))\right)\dfrac{\epsilon}{\mathcal{H}(y)-c+\epsilon},&\mbox{if
}\mathcal{H}(y)>c\geqslant\mathcal{H}(x);\\\
\dfrac{\mathcal{H}(x)-c+\epsilon}{\mathcal{H}(y)-c+\epsilon},&\mbox{if
}\mathcal{H}(y)>\mathcal{H}(x)>c.\end{cases}$

This resulting dynamics $M^{f}$ coincides with the energy transformation
method introduced by Catoni (1998, 1996) on
$\\{\mathcal{H}(y)>\mathcal{H}(x)>c\\}$, which is based on logarithmic
Hamiltonian. We refer readers to Section 5 for a more detailed account on the
connection between landscape modification and Catoni’s energy transformation.

###  2.2. Quadratic $f$: Metropolis-Hastings with $\arctan$ Hamiltonian

In this subsection, we take $f(u)=u^{2}$. In this case, the effect of
landscape modification gives an inverse-tangent-transformed Hamiltonian
whenever $\mathcal{H}(x)>c$.

For $x,y\in\\{\mathcal{H}(y)>\mathcal{H}(x)\geqslant c\\}$, since

$\int_{\mathcal{H}(x)}^{\mathcal{H}(y)}\frac{1}{(u-c)^{2}+\epsilon}\,du=\sqrt{\beta}\left(\arctan\left(\sqrt{\beta}(\mathcal{H}(y)-c)\right)-\arctan\left(\sqrt{\beta}(\mathcal{H}(x)-c)\right)\right),$

and substituting it back into (2.6) gives

$\displaystyle\exp\left(-(\mathcal{H}_{\epsilon,c}^{f}(y)-\mathcal{H}_{\epsilon,c}^{f}(x))_{+}\right)$
$\displaystyle=\begin{cases}1,&\mbox{if
}\mathcal{H}(y)\leqslant\mathcal{H}(x);\\\
\exp\left(-\beta(\mathcal{H}(y)-\mathcal{H}(x))\right),&\mbox{if
}c\geqslant\mathcal{H}(y)>\mathcal{H}(x);\\\
\exp\left(-\beta(c-\mathcal{H}(x))-\sqrt{\beta}\arctan\left(\sqrt{\beta}(\mathcal{H}(y)-c)\right)\right),&\mbox{if
}\mathcal{H}(y)>c\geqslant\mathcal{H}(x);\\\
\sqrt{\beta}\left(\arctan\left(\sqrt{\beta}(\mathcal{H}(x)-c)\right)-\arctan\left(\sqrt{\beta}(\mathcal{H}(y)-c)\right)\right),&\mbox{if
}\mathcal{H}(y)>\mathcal{H}(x)>c.\end{cases}$

###  2.3. Square root $f$: Metropolis-Hastings with sum of square root and
logarithmic Hamiltonian

In the final example, we let $f(u)=\sqrt{u}$ for $u\geqslant 0$. Note that
this choice of $f$ does not satisfy $f^{\prime}(0)=0$ as in Assumption 2.1.
For $x,y\in\\{\mathcal{H}(y)>\mathcal{H}(x)\geqslant c\\}$, consider the
integral

$\int_{\mathcal{H}(x)}^{\mathcal{H}(y)}\frac{1}{\sqrt{u-c}+\epsilon}\,du=2\left(\left(\sqrt{\mathcal{H}(y)-c}-\sqrt{\mathcal{H}(x)-c}\right)-\epsilon\ln\left(\dfrac{\sqrt{\mathcal{H}(y)-c}+\epsilon}{\sqrt{\mathcal{H}(x)-c}+\epsilon}\right)\right),$

putting the expression back into (2.6) gives

$\displaystyle\exp\left(-(\mathcal{H}_{\epsilon,c}^{f}(y)-\mathcal{H}_{\epsilon,c}^{f}(x))_{+}\right)$
$\displaystyle=\begin{cases}1,&\mbox{if
}\mathcal{H}(y)\leqslant\mathcal{H}(x);\\\
\exp\left(-\beta(\mathcal{H}(y)-\mathcal{H}(x))\right),&\mbox{if
}c\geqslant\mathcal{H}(y)>\mathcal{H}(x);\\\
\exp\left(-\beta(c-\mathcal{H}(x))-2\sqrt{\mathcal{H}(y)-c}\right)\left(\dfrac{\sqrt{\mathcal{H}(y)-c}+\epsilon}{\epsilon}\right)^{2\epsilon},&\mbox{if
}\mathcal{H}(y)>c\geqslant\mathcal{H}(x);\\\
\exp\left(2\sqrt{\mathcal{H}(x)-c}-2\sqrt{\mathcal{H}(y)-c}\right)\left(\dfrac{\sqrt{\mathcal{H}(y)-c}+\epsilon}{\sqrt{\mathcal{H}(x)-c}+\epsilon}\right)^{2\epsilon},&\mbox{if
}\mathcal{H}(y)>\mathcal{H}(x)>c.\end{cases}$

###  2.4. A Metropolised Ehrenfest urn with landscape modification

This section serves as a warm-up example before we discuss the more
complicated Curie-Weiss model in Section 3, and our exposition follows closely
as that in (Deuschel and Mazza, 1994, Section $5.1.2$). Let us first briefly
fix the setting. We consider the state space $\mathcal{X}=\\{0,1,\ldots,d\\}$
with $d\in\mathbb{N}$ and take a linear Hamiltonian $\mathcal{H}(x)=x$, where
$\mathcal{H}_{min}=0$. The proposal birth-death chain has generator $Q$ given
by $Q(x,x+1)=1-x/d$, $Q(x,x-1)=x/d$, $Q(x,x)=-1$ and zero otherwise, and we
note that the stationary measure of $Q$ is $\mu(x)\propto 2^{-d}{d\choose x}$.
With these choices, the classical Metropolised dynamics is
$M^{0}_{\epsilon}(x,x+1)=Q(x,x+1)e^{-\beta}$,
$M^{0}_{\epsilon}(x,x-1)=Q(x,x-1)$ and $\pi^{0}(x)\propto e^{-\beta x}\mu(x)$.
It is shown in (Deuschel and Mazza, 1994, equation $(5.1.1)$) that

(2.7)
$\displaystyle\lambda_{2}(-M^{0}_{\epsilon})\leqslant\lambda_{2}(-Q)\dfrac{1}{\sum_{x=0}^{d}e^{-\beta
x}\mu(x)}=\dfrac{d}{2}\dfrac{2^{d}}{(1+e^{-\beta})^{d}}.$

At a fixed inverse temperature $\beta$, we note that the upper bound in (2.7)
is exponential in $d$.

Now, we consider the landscape modified Metropolis-Hastings with $f(x)=x$ and
$c=1$. With these parameters, we compute

$\mathcal{H}(x)=\int_{0}^{x}\dfrac{1}{(u-1)_{+}+\epsilon}\,du=\beta+\ln\left(\dfrac{(x-1)_{+}+\epsilon}{\epsilon}\right).$

Using (Deuschel and Mazza, 1994, equation $(5.1.1)$) leads to

(2.8)
$\displaystyle\lambda_{2}(-M^{f}_{\epsilon,c=1})\leqslant\lambda_{2}(-Q)\dfrac{1}{\sum_{x=0}^{d}e^{-\mathcal{H}(x)}\mu(x)}=\dfrac{d}{2}\dfrac{2^{d}e^{\beta}}{\frac{\epsilon}{\lfloor
d/2\rfloor-1+\epsilon}{d\choose{\lfloor d/2\rfloor}}}\sim d^{3}\beta
e^{\beta},$

where we use the Stirling’s formula that gives for large enough $d$,

$\displaystyle{d\choose{\lfloor d/2\rfloor}}$
$\displaystyle\sim\dfrac{2^{d}}{\sqrt{\pi\lfloor d/2\rfloor}}.$

As a result, the upper bound in (2.8) gives a polynomial dependency on $d$, at
the tradeoff of an exponential dependency on $\beta$. In retrospect this
result is not surprising, since we are working with a logarithmic Hamiltonian
and hence the asymptotics is in the polynomial of $d$ instead of $2^{d}$.

##  3\. The Curie-Weiss model with landscape modification

In this section, we demonstrate the power of landscape modification by
revisiting the Curie-Weiss (CW) model. With appropriate choice of parameters,
the landscape of the CW free energy is modified and the local minimum is
eliminated while the global minimum is preserved on the transformed function.
As a result, landscape modification convexifies the free energy from a double-
well to a single-well as a function of the magnetization.

Let us first recall the setting of the CW model of a ferromagnet with external
field $h\in\mathbb{R}$ and fix a few notations. We shall follow the setting as
in (Bovier and den Hollander, 2015, Chapter $13,14$). Let
$\mathcal{X}=\\{-1,1\\}^{N}$ be the set of possible configurations of the CW
model with $N\in\mathbb{N}$. The CW Hamiltonian is given by, for
$\sigma=(\sigma_{i})_{i=1}^{N}\in\mathcal{X}$,

$H_{N}(\sigma):=-\dfrac{1}{2N}\sum_{i,j=1}^{n}\sigma_{i}\sigma_{j}-h\sum_{i=1}^{N}\sigma_{i}=-\dfrac{N}{2}m_{N}(\sigma)^{2}-hNm_{N}(\sigma)=:NE\left(m_{N}(\sigma)\right),$

where $m_{N}(\sigma)=(1/N)\sum_{i=1}^{N}\sigma_{i}$ is the empirical
magnetization. Consider the continuized Glauber dynamics by picking a node
uniformly at random and flipping the sign of the selected spin, while
targeting the Gibbs distribution with the CW Hamiltonian $H_{N}$ at inverse
temperature $\beta$. The resulting Metropolis dynamics is given by

$P_{\epsilon,N}(\sigma,\sigma^{\prime})=\begin{cases}(1/N)e^{-\beta(H_{N}(\sigma^{\prime})-H_{N}(\sigma))_{+}},&\mbox{if
}\left\lVert\sigma-\sigma^{\prime}\right\rVert_{1}=2;\\\
-\sum_{\eta:\eta\neq\sigma}P_{\epsilon,N}(\sigma,\eta),&\mbox{if
}\sigma=\sigma^{\prime};\\\ 0,&\mbox{otherwise,}\end{cases}$

where $\left\lVert\cdot\right\rVert_{1}$ is the $l^{1}$ norm on $\mathcal{X}$.

The dynamics of the empirical magnetization $(m^{0}(t))_{t\geqslant 0}$ can be
described by lumping the Glauber dynamics to give

$\displaystyle
M^{0}_{N}(m,m^{\prime})=M^{0}_{\epsilon,N}(m,m^{\prime})=\begin{cases}\frac{1-m}{2}e^{-\beta
N(E(m^{\prime})-E(m))_{+}},&\mbox{if }m^{\prime}=m+2N^{-1};\\\
\frac{1+m}{2}e^{-\beta N(E(m^{\prime})-E(m))_{+}},&\mbox{if
}m^{\prime}=m-2N^{-1};\\\ -\sum_{m^{\prime}:m^{\prime}\neq
m}M^{0}_{\epsilon,N}(m,m^{\prime}),&\mbox{if }m=m^{\prime};\\\
0,&\mbox{otherwise.}\end{cases}$

on the state space $\Gamma_{N}:=\\{-1,-1+2N^{-1},\ldots,1-2N^{-1},1\\}$ with
the image Gibbs distribution

$\pi^{0}_{N}(m)=\pi^{0}_{\epsilon,N}(m)\propto e^{-\beta
NE(m)}{N\choose\frac{1+m}{2}N}2^{-N},\quad m\in\Gamma_{N},$

as the stationary distribution. Note that the dependency on $\epsilon$ is
suppressed in the notations of $M^{0}_{N}$ and $\pi^{0}_{N}$. Denote by

$\displaystyle I_{N}(m)$
$\displaystyle:=-\dfrac{1}{N}\ln\left({N\choose\frac{1+m}{2}N}2^{-N}\right),$
$\displaystyle I(m)$
$\displaystyle:=\dfrac{1}{2}(1+m)\ln(1+m)+\dfrac{1}{2}(1-m)\ln(1-m),$
$\displaystyle g_{\epsilon,N}(m)$ $\displaystyle:=E(m)+\epsilon I_{N}(m),$

where $I(m)$ is the Cramér rate function for coin tossing. As a result, the
image Gibbs distribution can be written as

$\displaystyle\pi^{0}_{\epsilon,N}(m)$ $\displaystyle\propto e^{-\beta
Ng_{\epsilon,N}(m)},$ $\displaystyle\lim_{N\to\infty}I_{N}(m)$
$\displaystyle=I(m),$ $\displaystyle g_{\epsilon}(m)$
$\displaystyle:=\lim_{N\to\infty}g_{\epsilon,N}(m)=E(m)+\epsilon I(m).$

$g_{\epsilon}$ is called the free energy of the CW model. The stationary
point(s) of $g_{\epsilon}$ satisfies the classical mean-field equation

(3.1) $\displaystyle m=\tanh(\beta(m+h)).$

To seek the ground state(s) of the free energy, we consider modifying the
landscape of the CW Hamiltonian from $H_{N}$ to

(3.2) $\displaystyle E^{f}_{\epsilon,c}(m)$
$\displaystyle:=\int_{d}^{E(m)}\dfrac{1}{f((u-c)_{+})+\epsilon}\,du,$ (3.3)
$\displaystyle H^{f}_{\epsilon,c,N}(\sigma)$
$\displaystyle:=NE^{f}_{\epsilon,c}(m(\sigma)),$

where $d\in\mathbb{R}$ can be chosen arbitrarily since we are only interested
in the difference of $E^{f}_{\epsilon,c}$. The infinitesimal generator of the
magnetization $(m^{f}(t))_{t\geqslant 0}$ is

$\displaystyle
M^{f}_{\epsilon,c,N}(m,m^{\prime})=\begin{cases}\frac{1-m}{2}e^{-N(E^{f}_{\epsilon,c}(m^{\prime})-E^{f}_{\epsilon,c}(m))_{+}},&\mbox{if
}m^{\prime}=m+2N^{-1};\\\
\frac{1+m}{2}e^{-N(E^{f}_{\epsilon,c}(m^{\prime})-E^{f}_{\epsilon,c}(m))_{+}},&\mbox{if
}m^{\prime}=m-2N^{-1};\\\ -\sum_{m^{\prime}:m^{\prime}\neq
m}M^{f}_{\epsilon,c,N}(m,m^{\prime}),&\mbox{if }m=m^{\prime};\\\
0,&\mbox{otherwise,}\end{cases}$

with stationary distribution

$\pi^{f}_{\epsilon,c,N}(m)\propto
e^{-NE^{f}_{\epsilon,c,N}(m)}{N\choose\frac{1+m}{2}N}2^{-N}=e^{-Ng^{f}_{\epsilon,c,N}(m)},\quad
m\in\Gamma_{N},$

where

$\displaystyle g^{f}_{\epsilon,c,N}(m)$
$\displaystyle:=E^{f}_{\epsilon,c}(m)+I_{N}(m).$

By taking the limit $N\to\infty$, the free energy in the landscape modified CW
model is therefore

$g^{f}_{\epsilon,c}(m):=E^{f}_{\epsilon,c}(m)+I(m).$

Setting the derivative of $g^{f}_{\epsilon,c}$ equals to zero gives the
landscape modified mean-field equation:

(3.4) $\displaystyle m$
$\displaystyle=\tanh\left(\dfrac{m+h}{f((E(m)-c)_{+})+\epsilon}\right).$

Observe that if we take $f=0$, then (3.4) reduces to the classical mean-field
equation in (3.1).

###  3.1. Main results

Without loss of generality, assume the external magnetic field is $h<0$. In
the subcritical regime where $\beta>1$, it is known that there are two local
minima of $g_{\epsilon}$. We denote the global minimum of $g_{\epsilon}$ by
$m_{-}^{*}<0$ and the other local minimum by $m_{+}^{*}>0$, where
$|m_{-}^{*}|>m_{+}^{*}$, and let $z^{*}$ be the saddle point between
$m_{-}^{*}$ and $m_{+}^{*}$. We also write $m_{-}^{*}(N)$ (resp.
$m_{+}^{*}(N)$) to be the closest point in Euclidean distance on $\Gamma_{N}$
to $m_{-}^{*}$ (resp. $m_{+}^{*}$).

######  Theorem 3.1 (Landscape modification in the subcritical regime).

Suppose $\beta>1$, $h<0$ and $f,c$ are chosen as in Assumption 2.1.

  1. (1)

[Convexification of the free energy $g_{\epsilon}$ and subexponential mean
crossover time] If we choose $c\in[E(m_{-}^{*}),E(m_{+}^{*}))$, $c<h^{2}/2$,
$-h-\sqrt{h^{2}-2c}\leqslant z^{*}$ and for
$m\in[-h-\sqrt{h^{2}-2c},-h+\sqrt{h^{2}-2c}]$,

$m>\tanh\left(\dfrac{m+h}{f((E(m)-c)_{+})+\epsilon}\right),$

then $m_{-}^{*}$ is the only stationary point of the modified free energy
$g^{f}_{\epsilon,c}$, which is a global minimum. Consequently,

(3.5)
$\displaystyle\lim_{N\to\infty}\dfrac{1}{N}\log\mathbb{E}_{m_{+}^{*}(N)}\left(\tau^{f}_{m_{-}^{*}(N)}\right)=0.$

  2. (2)

Assume in addition that $f$ is twice differentiable and satisfies
$f^{\prime}(0)=f^{\prime\prime}(0)=0$. If we choose
$c\in[E(m_{+}^{*}),E(z^{*})]$, then there exists
$\mathbf{z}^{*}=\arg\max_{m_{-}^{*}\leqslant m\leqslant
m_{+}^{*}}g^{f}_{\epsilon,c}(m)$ and as $N\to\infty$,

$\displaystyle\mathbb{E}_{m_{+}^{*}(N)}\left(\tau^{f}_{m_{-}^{*}(N)}\right)$
$\displaystyle=\exp\left(N(g_{\epsilon,c}^{f}(\mathbf{z}^{*})-g_{\epsilon,c}^{f}(m_{+}^{*}))\right)$
$\displaystyle\quad\times\frac{2}{1-|\mathbf{z}^{*}|}\sqrt{\frac{1-\mathbf{z}^{*2}}{1-m_{+}^{*2}}}\frac{2\pi
N/4}{\sqrt{\left(-g_{\epsilon,c}^{f\prime\prime}\left(\mathbf{z}^{*}\right)\right)g_{\epsilon,c}^{f\prime\prime}\left(m_{+}^{*}\right)}}(1+o(1)).$

Consequently,

$\displaystyle\lim_{N\to\infty}\dfrac{1}{N}\log\mathbb{E}_{m_{+}^{*}(N)}\left(\tau^{f}_{m_{-}^{*}(N)}\right)$
$\displaystyle=g_{\epsilon,c}^{f}(\mathbf{z}^{*})-g_{\epsilon,c}^{f}(m_{+}^{*})$
$\displaystyle=\beta(c-E(m_{+}^{*}))+\int_{c}^{E(\mathbf{z}^{*})}\dfrac{1}{f((u-c)_{+})+\epsilon}\,du+\left(I(\mathbf{z}^{*})-I(m_{+}^{*})\right)$
$\displaystyle\leqslant\beta(g_{\epsilon}(z^{*})-g_{\epsilon}(m_{+}^{*}))=\lim_{N\to\infty}\dfrac{1}{N}\log\mathbb{E}_{m_{+}^{*}(N)}\left(\tau_{m_{-}^{*}(N)}\right).$

Before we present the proof, we interpret the results in Theorem 3.1
intuitively: in item (1), on one hand we would like to choose $c$ small enough
such that the mapping

$m\mapsto\tanh\left(\dfrac{m+h}{f((E(m)-c)_{+})+\epsilon}\right)$

is flattened and only intersects with the straight line $m\mapsto m$ at the
global minimum $m_{-}^{*}$. In this way the landscape of $g^{f}_{\epsilon,c}$
is transformed from a double-well to a single-well, while the location of the
global minimum at $m_{-}^{*}$ is preserved as that in the original landscape
$g_{\epsilon}$. This is illustrated in Figure 1 and Figure 2. On the other
hand, we cannot choose $c$ to be too small if we are interested in seeking the
ground state of $g_{\epsilon}$, since otherwise if $c<E(m_{-}^{*})$ then
$m_{-}^{*}$ may no longer be the global minimum in the transformed free energy
$g^{f}_{\epsilon,c}$. In Theorem 3.1 item (2), we choose a larger value of $c$
compared with that in item (1). Although the transformed free energy
$g^{f}_{\epsilon,c}$ is not a convex function, it has a smaller critical
height than the original free energy $g_{\epsilon}$.

The power of landscape modification or energy transformation lies in tuning
the parameter $c$ appropriately. One way to tune $c$ is to use the running
minimum generated by the algorithm on the original free energy $g_{\epsilon}$.
Suppose we start in the well containing the local minimum $m_{+}^{*}$, and
setting $c$ to be the running minimum eventually gives $c=E(m_{+}^{*})$, and
hence Theorem 3.1 item (2) can be applied and the critical height on the
modified landscape is reduced.

We illustrate Theorem 3.1 with a concrete numerical example in Figure 1 and
Figure 2, where we take $h=-0.05$ and $f(x)=x$ at inverse temperature
$\beta=1.5$. We numerically compute that $m_{-}^{*}=-0.8863$,
$m_{+}^{*}=0.8188$ and $z^{*}=0.1524$. As a result we have
$E(m_{-}^{*})=-0.4371$, $E(m_{+}^{*})=-0.2943$ and $E(z^{*})=-0.004$. In the
leftmost plot of Figure 1 and Figure 2, we choose
$c=-0.4\in[E(m_{-}^{*}),E(m_{+}^{*}))$. We numerically check that the
conditions in Theorem 3.1 item (1) are satisfied, and we see that the blue
curve and the orange curve share the same location of the global minimum. In
the rightmost plot of Figure 1 and Figure 2, we choose
$c=-0.2\in[E(m_{+}^{*}),E(z^{*})]$. We see that the blue curve and the red
curve share the same locations of the two local minima, while the critical
height is smaller than that in the original landscape $g_{\epsilon}$.

Figure 1. Plots of the free energy $g_{\epsilon}$ and the modified free energy
$g^{f}_{\epsilon,c}+E_{min}$ with $h=-0.05$ and $f(x)=x$ at inverse
temperature $\beta=1.5$, where $E_{min}=\min_{m\in[-1,1]}E(m)$. We shift the
modified free energy by $E_{min}$ so that it is on the same scale as the
original free energy $g_{\epsilon}$. Figure 2. Plots of the mean-field
equation (3.1) and the modified mean-field equation (3.4) with $h=-0.05$ and
$f(x)=x$ at inverse temperature $\beta=1.5$.

###  3.2. Proof of Theorem 3.1

Before we give the proof, we first recall the concept of critical height. In
Section 2, we define the critical height of the Hamiltonian function. However
here in the CW model with landscape modification we are interested in the free
energy $g^{f}_{\epsilon,c,N}$. As a result we define the analogous concepts by
inserting a subscript of $N$. The highest value of the free energy
$g^{f}_{\epsilon,c,N}$ along a path $\gamma\in\chi^{x,y}$, known as the
elevation, is defined to be

$\mathrm{Elev}^{f}_{\epsilon,c,N}(\gamma)=\max\\{g^{f}_{\epsilon,c,N}(\gamma_{i});~{}\gamma_{i}\in\gamma\\},$

and the lowest possible highest elevation along path(s) from $x$ to $y$ is

$G^{f}_{\epsilon,c,N}(x,y):=\min\\{\mathrm{Elev}^{f}_{\epsilon,c,N}(\gamma);~{}\gamma\in\chi^{x,y}\\}.$

For $M^{f}_{\epsilon,c,N}$, the associated critical height is defined to be

$\displaystyle H^{f}_{\epsilon,c,N}$
$\displaystyle:=\max_{x,y\in\Gamma_{N}}\\{G^{f}_{\epsilon,c,N}(x,y)-g^{f}_{\epsilon,c,N}(x)-g^{f}_{\epsilon,c,N}(y)+\min_{x\in\Gamma_{N}}g^{f}_{\epsilon,c,N}(x)\\}.$

Similarly, for $M^{0}_{\epsilon,N}$ its critical height is

$\displaystyle H^{0}_{\epsilon,N}$
$\displaystyle:=\max_{x,y\in\Gamma_{N}}\\{G^{0}_{\epsilon,N}(x,y)-g_{\epsilon,N}(x)-g_{\epsilon,N}(y)+\min_{x\in\Gamma_{N}}g_{\epsilon,N}(x)\\}.$

[Proof of Theorem 3.1. ] First, we prove item (1). First, we note that
$\\{E(m)\geqslant c\\}=\\{m\in[-h-\sqrt{h^{2}-2c},-h+\sqrt{h^{2}-2c}]\\}$. On
this interval,

$\dfrac{d}{dm}g^{f}_{\epsilon,c}(m)=\operatorname{arctanh}(m)-\dfrac{m+h}{f((E(m)-c)_{+})+\epsilon}>0,$

and hence the modified free energy is strictly increasing on this interval. On
the interval $\\{m>-h+\sqrt{h^{2}-2c}\\}$,
$\dfrac{d}{dm}g^{f}_{\epsilon,c}(m)=\dfrac{d}{dm}g_{\epsilon}(m)>0$ as the
original free energy is strictly increasing. On the interval
$\\{m<-h-\sqrt{h^{2}-2c}\\}$, we also have
$\dfrac{d}{dm}g^{f}_{\epsilon,c}(m)=\dfrac{d}{dm}g_{\epsilon}(m)$. Thus, with
these parameter choices, the only stationary point of $g^{f}_{\epsilon,c}$ is
$m^{*}_{-}$, which is the global minimum.

Next, we proceed to prove (3.5). According to (Löwe, 1996, Theorem $2.1$), for
$\xi_{1}(N)$ a polynomial function in $N$, we have

$\dfrac{1}{\lambda_{2}(-M^{f}_{\epsilon,c,N})}\leqslant\xi_{1}(N)e^{NH^{f}_{\epsilon,c,N}}.$

Now, using the random target lemma (Levin and Peres, 2017, Lemma $12.17$) and
the above inequality lead to

(3.6)
$\displaystyle\pi^{f}_{\epsilon,c,N}(m^{*}_{-}(N))\mathbb{E}_{m_{+}^{*}(N)}\left(\tau^{f}_{m_{-}^{*}(N)}\right)\leqslant\sum_{y\in\Gamma_{N}}\pi^{f}_{\epsilon,c,N}(y)\mathbb{E}_{m_{+}^{*}(N)}\left(\tau^{f}_{y}\right)\leqslant(|\Gamma_{N}|-1)\dfrac{1}{\lambda_{2}(-M^{f}_{\epsilon,c,N})}\leqslant
N\xi_{1}(N)e^{NH^{f}_{\epsilon,c,N}}.$

Now, let $\overline{m}(N):=\arg\min g^{f}_{\epsilon,c,N}(m)$ and compute

$\displaystyle
g^{f}_{\epsilon,c,N}(m^{*}_{-}(N))-g^{f}_{\epsilon,c,N}(\overline{m}(N))$
$\displaystyle=E^{f}_{\epsilon,c}(m^{*}_{-}(N))-E^{f}_{\epsilon,c}(\overline{m}(N))+I_{N}(m^{*}_{-}(N))-I_{N}(\overline{m}(N))$
$\displaystyle=E^{f}_{\epsilon,c}(m^{*}_{-}(N))-E^{f}_{\epsilon,c}(\overline{m}(N))$
$\displaystyle\quad+I_{N}(m^{*}_{-}(N))-I(m^{*}_{-}(N))+I(m^{*}_{-}(N))-I_{N}(\overline{m}(N))$
$\displaystyle=E^{f}_{\epsilon,c}(m^{*}_{-}(N))-E^{f}_{\epsilon,c}(\overline{m}(N))$
$\displaystyle\quad+[1+o(1)]\frac{1}{2N}\ln\left(\frac{\pi
N\left(1-m^{*}_{-}(N)^{2}\right)}{2}\right)$
$\displaystyle\quad+I(m_{-}^{*}(N))-I(\overline{m}(N))$
$\displaystyle\quad-[1+o(1)]\frac{1}{2N}\ln\left(\frac{\pi
N\left(1-\overline{m}(N)^{2}\right)}{2}\right)$ $\displaystyle\rightarrow
0\quad\text{as}\,N\to\infty,$

where we use (Bovier and den Hollander, 2015, equation $(13.2.5)$) in the
third equality, and $m_{-}^{*}(N),\overline{m}(N)\to m_{-}^{*}$ as
$N\to\infty$. Together with (3.6) yields

(3.7)
$\displaystyle\limsup_{N\to\infty}\mathbb{E}_{m_{+}^{*}(N)}\left(\tau^{f}_{m_{-}^{*}(N)}\right)\leqslant\lim_{N\to\infty}H^{f}_{\epsilon,c,N}=0.$

On the other hand, as the magnetization $(m^{f}(t))_{t\geqslant 0}$ is a
birth-death process, using (Bovier and den Hollander, 2015, equation
$(13.2.2)$) the mean hitting time can be calculated explicitly as

$\displaystyle\mathbb{E}_{m_{+}^{*}(N)}\left(\tau^{f}_{m_{-}^{*}(N)}\right)$
$\displaystyle=\sum_{m,m^{\prime}\in\Gamma_{N},m\leqslant m^{\prime}\atop
m_{-}^{*}(N)<m\leqslant
m_{+}^{*}(N)}\frac{\pi^{f}_{\epsilon,c,N}\left(m^{\prime}\right)}{\pi^{f}_{\epsilon,c,N}(m)}\frac{1}{M^{f}_{\epsilon,c,N}\left(m,m-2N^{-1}\right)}$
$\displaystyle\geqslant\dfrac{1}{M^{f}_{\epsilon,c,N}\left(m_{+}^{*}(N),m_{+}^{*}(N)-2N^{-1}\right)}=\dfrac{2}{1+m_{+}^{*}(N)}e^{N(E^{f}_{\epsilon,c}(m_{+}^{*}(N)-2N^{-1})-E^{f}_{\epsilon,c}(m))_{+}}$
$\displaystyle\geqslant\dfrac{2}{1+m_{+}^{*}(N)}.$

As a result, as $m_{+}^{*}(N)\to m_{+}^{*}$ we have

(3.8)
$\displaystyle\liminf_{N\to\infty}\mathbb{E}_{m_{+}^{*}(N)}\left(\tau^{f}_{m_{-}^{*}(N)}\right)\geqslant
0.$

Using both (3.8) and (3.7) gives (3.5).

Next, we prove item (2), which follow closely with the proof of (Bovier and
den Hollander, 2015, Theorem $13.1$). Since we choose
$c\in[E(m_{+}^{*}),E(z^{*})]$, then we have
$E(m_{-}^{*})-c<E(m_{+}^{*})-c\leqslant 0$, and hence the landscape modified
mean-field equation (3.4) has at least two solutions $m_{+}^{*}$ and
$m_{-}^{*}$, which are exactly the same as the original mean-field equation
(3.1). As the landscape modified mean-field equation is continuous in $m$,
there exists $\mathbf{z}^{*}=\arg\max_{m_{-}^{*}\leqslant m\leqslant
m_{+}^{*}}g^{f}_{\epsilon,c}(m)$ which also satisfies (3.4). Now, for
$m\in\Gamma_{N}$ we consider

$\displaystyle
N\left(E^{f}_{\epsilon,c}(m-2N^{-1})-E^{f}_{\epsilon,c}(m)\right)$
$\displaystyle=N\int_{E(m)}^{E(m)+2N^{-1}(m+h-N^{-1})}\dfrac{1}{f((u-c)_{+})+\epsilon}\,du$
$\displaystyle\rightarrow\dfrac{2(m+h)}{f((E(m)-c)_{+})+\epsilon}\quad\text{as
}N\to\infty.$

If we take $N\to\infty$ and $m\rightarrow\mathbf{z}^{*}$, we obtain

$\displaystyle\frac{1}{M^{f}_{\epsilon,c,N}\left(m,m-2N^{-1}\right)}\to\dfrac{2}{1+\mathbf{z}^{*}}\exp\left(\dfrac{2(\mathbf{z}^{*}+h)_{+}}{f((E(\mathbf{z}^{*})-c)_{+})+\epsilon}\right)=\dfrac{2}{1-|\mathbf{z}^{*}|},$

since if $\mathbf{z}^{*}>0$, then $\mathbf{z}^{*}+h>0$ and satisfies the mean-
field equation (3.4). Using the mean hitting time formula again leads to, for
any $\delta>0$,

$\displaystyle\mathbb{E}_{m_{+}^{*}(N)}\left(\tau^{f}_{m_{-}^{*}(N)}\right)$
$\displaystyle=\sum_{m,m^{\prime}\in\Gamma_{N},m\leqslant m^{\prime}\atop
m_{-}^{*}(N)<m\leqslant
m_{+}^{*}(N)}\frac{\pi^{f}_{\epsilon,c,N}\left(m^{\prime}\right)}{\pi^{f}_{\epsilon,c,N}(m)}\frac{1}{M^{f}_{\epsilon,c,N}\left(m,m-2N^{-1}\right)}$
$\displaystyle=e^{N\left[g^{f}_{\epsilon,c,N}\left(\mathbf{z}^{*}\right)-g^{f}_{\epsilon,c,N}\left(m_{+}^{*}\right)\right]}\frac{2}{1-|\mathbf{z}^{*}|}[1+o(1)]$
(3.9)
$\displaystyle\quad\times\sum_{m,m^{\prime}\in\Gamma_{N}\atop\left|m-\mathbf{z}^{*}\right|<\delta,\left|m^{\prime}-m_{+}^{*}\right|<\delta}\mathrm{e}^{N\left[g^{f}_{\epsilon,c,N}(m)-g^{f}_{\epsilon,c,N}\left(\mathbf{z}^{*}\right)\right]-N\left[g^{f}_{\epsilon,c,N}\left(m^{\prime}\right)-g^{f}_{\epsilon,c,N}\left(m_{+}^{*}\right)\right]}.$

Using the Stirling’s formula and the same argument as in (Bovier and den
Hollander, 2015, equation $(13.2.7)$) yield

$\displaystyle
e^{N\left[g^{f}_{\epsilon,c,N}\left(\mathbf{z}^{*}\right)-g^{f}_{\epsilon,c,N}\left(m_{+}^{*}\right)\right]}$
$\displaystyle=(1+o(1))e^{N\left[g^{f}_{\epsilon,c}\left(\mathbf{z}^{*}\right)-g^{f}_{\epsilon,c}\left(m_{+}^{*}\right)\right]}\sqrt{\dfrac{1-\mathbf{z}^{*2}}{1-m_{+}^{*2}}}$

followed by substitution to (3.2) gives

$\displaystyle\mathbb{E}_{m_{+}^{*}(N)}\left(\tau^{f}_{m_{-}^{*}(N)}\right)$
$\displaystyle=e^{N\left[g^{f}_{\epsilon,c}\left(\mathbf{z}^{*}\right)-g^{f}_{\epsilon,c}\left(m_{+}^{*}\right)\right]}\frac{2}{1-|\mathbf{z}^{*}|}\sqrt{\dfrac{1-\mathbf{z}^{*2}}{1-m_{+}^{*2}}}[1+o(1)]$
(3.10)
$\displaystyle\quad\times\sum_{m,m^{\prime}\in\Gamma_{N}\atop\left|m-\mathbf{z}^{*}\right|<\delta,\left|m^{\prime}-m_{+}^{*}\right|<\delta}\sqrt{\dfrac{1-m^{2}}{1-\mathbf{z}^{*2}}}\sqrt{\dfrac{1-m^{*2}_{+}}{1-m^{\prime
2}}}\mathrm{e}^{N\left[g^{f}_{\epsilon,c}(m)-g^{f}_{\epsilon,c}\left(\mathbf{z}^{*}\right)\right]-N\left[g^{f}_{\epsilon,c}\left(m^{\prime}\right)-g^{f}_{\epsilon,c}\left(m_{+}^{*}\right)\right]}.$

We proceed to use a Laplace method argument to handle the sum in (3.2). Note
that as $f$ is assumed to be twice-differentiable with
$f(0)=f^{\prime}(0)=f^{\prime\prime}(0)=0$, this implies $g^{f}_{\epsilon,c}$
is three-time differentiable, and applying the third-order Taylor expansion
gives

(3.11) $\displaystyle
g^{f}_{\epsilon,c}(m)-g^{f}_{\epsilon,c}\left(\mathbf{z}^{*}\right)$
$\displaystyle=\dfrac{(m-\mathbf{z}^{*})^{2}}{2}g^{f\prime\prime}_{\epsilon,c}(\mathbf{z}^{*})+\mathcal{O}\left((m-\mathbf{z}^{*})^{3}\right),$
(3.12) $\displaystyle
g^{f}_{\epsilon,c}\left(m^{\prime}\right)-g^{f}_{\epsilon,c}\left(m_{+}^{*}\right)$
$\displaystyle=\dfrac{(m^{\prime}-m_{+}^{*})^{2}}{2}g^{f\prime\prime}_{\epsilon,c}(m_{+}^{*})+\mathcal{O}\left((m^{\prime}-m_{+}^{*})^{3}\right),$

where we use
$g^{f\prime}_{\epsilon,c}(\mathbf{z}^{*})=g^{f\prime}_{\epsilon,c}(m_{+}^{*})=0$.
Now, we observe that the sum in (3.2) is

$\displaystyle\quad(1+o(1))\dfrac{N}{4}\int_{\mathbb{R}}\int_{\mathbb{R}}\exp\left[\frac{1}{2}g_{\epsilon,c}^{f\prime\prime}\left(\mathbf{z}^{*}\right)u^{2}-\frac{1}{2}g_{\epsilon,c}^{f\prime\prime}\left(m_{+}^{*}\right)u^{\prime
2}\right]\,dudu^{\prime}$
$\displaystyle=(1+o(1))\dfrac{N}{4}\frac{2\pi}{\sqrt{\left[-g_{\epsilon,c}^{f\prime\prime}\left(\mathbf{z}^{*}\right)\right]g_{\epsilon,c}^{f\prime\prime}\left(m_{+}^{*}\right)}},$

since $g_{\epsilon,c}^{f\prime\prime}\left(\mathbf{z}^{*}\right)<0$ and
$g_{\epsilon,c}^{f\prime\prime}\left(m_{+}^{*}\right)>0$.

###  3.3. Extension to the random field Curie-Weiss

In Section 3.1, we discuss the classical CW model with landscape modification
under fixed magnetic field. In this section, we aim at considering the random
field CW model with landscape modification, and discuss related metastability
results and its ground state free energy in such setting. Let us begin by
first recalling the random field CW model. We shall adapt the setting as in
Mathieu and Picco (1998). Let $(h_{i})_{i\in\mathbb{N}}$ be a sequence of
i.i.d. random variables with $\mathbb{P}(h_{i}=1)=\mathbb{P}(h_{i}=-1)=1/2$.
We consider the random Hamiltonian function given by, for a fixed $\theta>0$
and $\sigma\in\\{-1,1\\}^{N}$,

$\mathbf{H}_{N}(\sigma)=\mathbf{H}_{N}(\sigma,\omega):=-\dfrac{N}{2}\mathbf{m}_{N}(\sigma)^{2}-\theta\sum_{i=1}^{N}h_{i}(\omega)\sigma_{i}=-\dfrac{N}{2}(\mathbf{m}_{N}^{+}(\sigma)+\mathbf{m}_{N}^{-}(\sigma))^{2}-\theta
N(\mathbf{m}_{N}^{+}(\sigma)-\mathbf{m}_{N}^{-}(\sigma)),$

where $\mathbf{m}_{N}(\sigma):=(1/N)\sum_{i=1}^{N}\sigma_{i}$,
$\mathbf{m}_{N}^{+}(\sigma):=(1/N)\sum_{i=1;~{}h_{i}=1}^{N}\sigma_{i}$ and
$\mathbf{m}_{N}^{-}(\sigma):=(1/N)\sum_{i=1;~{}h_{i}=-1}^{N}\sigma_{i}$. In
the sequel, we shall suppress the dependency on $\omega$. Denote the Gibbs
measure at inverse temperature $\beta$ on $\\{-1,1\\}^{N}$ by

$\bm{\nu}_{N}(\sigma)\propto\exp\\{-\beta\mathbf{H}_{N}(\sigma)\\}.$

Let $N^{+}:=|\\{i;~{}h_{i}=+1\\}|$, $N^{-}:=|\\{i;~{}h_{i}=-1\\}|$ and define
the random set

$\mathbf{\Gamma}_{N}:=\left(-\frac{N^{+}}{N},-\frac{N^{+}}{N}+\frac{2}{N},\ldots,\frac{N^{+}}{N}\right)\times\left(-\frac{N^{-}}{N},-\frac{N^{-}}{N}+\frac{2}{N},\ldots,\frac{N^{-}}{N}\right).$

For $\mathbf{m}=(\mathbf{m}^{+},\mathbf{m}^{-})\in\bm{\Gamma}_{N}$, with
slight abuse of notation we write

$\mathbf{H}_{N}(\mathbf{m})=-\dfrac{N}{2}(\mathbf{m}^{+}+\mathbf{m}^{-})^{2}-\theta
N(\mathbf{m}^{+}-\mathbf{m}^{-})=:N\mathbf{E}(\mathbf{m}).$

Let $\bm{\pi}_{\epsilon,N}^{0}$ denote the image Gibbs measure of
$\bm{\nu}_{N}$ by $\mathbf{\Gamma}_{N}$, where

$\displaystyle\bm{\pi}_{\epsilon,N}^{0}(\mathbf{m})$
$\displaystyle\propto\exp\\{-\beta N\mathbf{g}_{\epsilon,N}(\mathbf{m})\\},$
$\displaystyle\mathbf{g}_{\epsilon,N}(\mathbf{m})$
$\displaystyle:=-\dfrac{1}{2}(\mathbf{m}^{+}+\mathbf{m}^{-})^{2}-\theta(\mathbf{m}^{+}-\mathbf{m}^{-})-\frac{1}{\beta
N}\log\left(\begin{array}[]{c}N^{+}\\\
\frac{N^{+}}{2}+\mathbf{m}^{+}\frac{N}{2}\end{array}\right)\left(\begin{array}[]{c}N^{-}\\\
\frac{N^{-}}{2}+\mathbf{m}^{-}\frac{N}{2}\end{array}\right).$

As $N\to\infty$, by the strong law of large number $\mathbf{g}_{\epsilon,N}$
converges almost surely to the free energy given by

$\mathbf{g}_{\epsilon}(\mathbf{m}):=-\dfrac{1}{2}(\mathbf{m}^{+}+\mathbf{m}^{-})^{2}-\theta(\mathbf{m}^{+}-\mathbf{m}^{-})+\frac{1}{2\beta}\left(I(2\mathbf{m}^{+})+I(2\mathbf{m}^{-})\right),$

where $I(m)$ is the Cramér rate function as introduced in Section 3. The
critical points of $\mathbf{g}_{\epsilon}$ satisfy

(3.13) $\displaystyle\mathbf{m}^{+}$
$\displaystyle=\dfrac{1}{2}\tanh(\beta(\mathbf{m}^{+}+\mathbf{m}^{-}+\theta)),$
(3.14) $\displaystyle\mathbf{m}^{-}$
$\displaystyle=\dfrac{1}{2}\tanh(\beta(\mathbf{m}^{+}+\mathbf{m}^{-}-\theta)).$

In this section, we shall only consider the subcritical regime where
$\beta>\cosh^{2}(\beta\theta)$. It can be shown (see e.g. Mathieu and Picco
(1998)) that there are exactly three critical points. Let $\mathbf{m}_{*}>0$
be the unique positive solution to the mean-field equation

$\mathbf{m}_{*}=\dfrac{1}{2}\left(\tanh(\beta(\mathbf{m}_{*}+\theta))+\tanh(\beta(\mathbf{m}_{*}-\theta))\right).$

The three critical points of $\mathbf{g}_{\epsilon}$ are given by

$\displaystyle\mathbf{m}_{0}$
$\displaystyle=\left(\frac{1}{2}\tanh(\beta\theta),-\frac{1}{2}\tanh(\beta\theta)\right),$
$\displaystyle\mathbf{m}_{1}$
$\displaystyle=\left(\frac{1}{2}\tanh\left(\beta\mathbf{m}_{*}+\beta\theta\right),\frac{1}{2}\tanh\left(\beta\mathbf{m}_{*}-\beta\theta\right)\right),$
$\displaystyle\mathbf{m}_{2}$
$\displaystyle=\left(\frac{1}{2}\tanh\left(-\beta\mathbf{m}_{*}+\beta\theta\right),-\frac{1}{2}\tanh\left(\beta\mathbf{m}_{*}+\beta\theta\right)\right),$

where $\mathbf{m}_{0}$ is the saddle point and $\mathbf{m}_{1},\mathbf{m}_{2}$
are the two global minima. Consider the continuized Glauber dynamics
$(\sigma_{N}(t))_{t\geqslant 0}$ by picking a node uniformly at random and
changing the sign of the selected spin, while targeting the Gibbs distribution
$\bm{\nu}_{N}$ at inverse temperature $\beta$. Denote by
$\mathbf{m}_{N}(t):=\mathbf{m}_{N}(\sigma_{N}(t))$ be the induced dynamics on
the magnetization, and its infiniteismal generator by
$\mathbf{M}^{0}_{\epsilon,N}$. This is proven to be a Markov chain in Mathieu
and Picco (1998), with stationary measure $\bm{\pi}^{0}_{\epsilon,N}$.

Now, let us consider the landscape modified Hamiltonian on $\bm{\Gamma}_{N}$:

(3.15) $\displaystyle\mathbf{E}^{f}_{\epsilon,c}(\mathbf{m})$
$\displaystyle:=\int_{d}^{\mathbf{E}(\mathbf{m})}\dfrac{1}{f((u-c)_{+})+\epsilon}\,du,$
(3.16) $\displaystyle\mathbf{H}^{f}_{\epsilon,c,N}(\mathbf{m})$
$\displaystyle:=N\mathbf{E}^{f}_{\epsilon,c}(\mathbf{m}),$

where $d\in\mathbb{R}$ can be chosen arbitrarily since we are only interested
in the difference of $\mathbf{E}^{f}_{\epsilon,c}$. The transformed image
Gibbs measure is therefore

$\displaystyle\bm{\pi}_{\epsilon,c,N}^{f}(\mathbf{m})$
$\displaystyle\propto\exp\\{-N\mathbf{g}^{f}_{\epsilon,c,N}(\mathbf{m})\\},$
$\displaystyle\mathbf{g}^{f}_{\epsilon,c,N}(\mathbf{m})$
$\displaystyle:=\mathbf{E}^{f}_{\epsilon,c}(\mathbf{m})-\frac{1}{N}\log\left(\begin{array}[]{c}N^{+}\\\
\frac{N^{+}}{2}+\mathbf{m}^{+}\frac{N}{2}\end{array}\right)\left(\begin{array}[]{c}N^{-}\\\
\frac{N^{-}}{2}+\mathbf{m}^{-}\frac{N}{2}\end{array}\right).$

The strong law of large number yields that as $N\to\infty$,
$\mathbf{g}^{f}_{\epsilon,c,N}$ converges almost surely to the transformed
free energy

$\mathbf{g}^{f}_{\epsilon,c}(\mathbf{m}):=\mathbf{E}^{f}_{\epsilon,c}(\mathbf{m})+\frac{1}{2}\left(I(2\mathbf{m}^{+})+I(2\mathbf{m}^{-})\right).$

The critical points of $\mathbf{g}^{f}_{\epsilon,c}$ satisfy the following
landscape modified mean-field equations:

(3.17) $\displaystyle\mathbf{m}^{+}$
$\displaystyle=\dfrac{1}{2}\tanh\left(\dfrac{\mathbf{m}^{+}+\mathbf{m}^{-}+\theta}{f((\mathbf{E}(\mathbf{m})-c)_{+})+\epsilon}\right),$
(3.18) $\displaystyle\mathbf{m}^{-}$
$\displaystyle=\dfrac{1}{2}\tanh\left(\dfrac{\mathbf{m}^{+}+\mathbf{m}^{-}-\theta}{f((\mathbf{E}(\mathbf{m})-c)_{+})+\epsilon}\right).$

Note that (3.17) and (3.18) reduce to the classical case (3.13) and (3.14) if
we take $f=0$. Consider the continuized Glauber dynamics
$(\sigma_{N}^{f}(t))_{t\geqslant 0}$ by picking a node uniformly at random and
changing the sign of the selected spin, while targeting the Gibbs distribution
with Hamiltonian $\mathbf{H}^{f}_{\epsilon,c,N}$ at inverse temperature $1$.
Denote by $\mathbf{m}_{N}^{f}(t):=\mathbf{m}^{f}_{N}(\sigma_{N}^{f}(t))$ be
the induced dynamics on the magnetization, and its infiniteismal generator by
$\mathbf{M}^{f}_{\epsilon,c,N}$, which is a Markov chain with stationary
measure $\bm{\pi}^{f}_{\epsilon,c,N}$.

In the following, we shall consider the case where
$c\in[\mathbf{E}(\mathbf{m}_{1}),\mathbf{E}(\mathbf{m}_{0})]$. It can be seen
that the two global minima of $\mathbf{g}^{f}_{\epsilon,c}$ remain to be
$\mathbf{m}_{1},\mathbf{m}_{2}$ with this choice of $c$. For any path
$\gamma^{\mathbf{m}_{1},\mathbf{m}_{0}}$ connecting $\mathbf{m}_{1}$ and
$\mathbf{m}_{0}$, we define

$\displaystyle\mathbf{m}_{3}(\gamma^{\mathbf{m}_{1},\mathbf{m}_{0}})$
$\displaystyle:=\arg\max\\{\mathbf{g}^{f}_{\epsilon,c}(\gamma_{i});~{}\gamma_{i}\in\gamma^{\mathbf{m}_{1},\mathbf{m}_{0}}\\},$
$\displaystyle\Delta\mathbf{g}^{f}_{\epsilon,c}$
$\displaystyle:=\min_{\gamma^{\mathbf{m}_{1},\mathbf{m}_{0}}}\mathbf{m}_{3}(\gamma^{\mathbf{m}_{1},\mathbf{m}_{0}})-\mathbf{g}^{f}_{\epsilon,c}(\mathbf{m}_{1})=\min_{\gamma^{\mathbf{m}_{1},\mathbf{m}_{0}}}\mathbf{m}_{3}(\gamma^{\mathbf{m}_{1},\mathbf{m}_{0}})-\mathbf{g}^{f}_{\epsilon,c}(\mathbf{m}_{0}),$

where $\Delta\mathbf{g}^{f}_{\epsilon,c}$ is the critical height on the
modified landscape. We also write $\Delta\mathbf{g}_{\epsilon}$ to denote the
critical height on the original landscape. Suppose that
$\Delta\mathbf{g}_{\epsilon}$ is attained at $\mathbf{m}_{4}$ so that
$\Delta\mathbf{g}_{\epsilon}=\mathbf{g}_{\epsilon}(\mathbf{m}_{4})-\mathbf{g}_{\epsilon}(\mathbf{m}_{0})$,
and we deduce

$\displaystyle\Delta\mathbf{g}^{f}_{\epsilon,c}\leqslant\mathbf{g}^{f}_{\epsilon,c}(\mathbf{m}_{4})-\mathbf{g}^{f}_{\epsilon,c}(\mathbf{m}_{0})$
$\displaystyle=\int_{\mathbf{E}(\mathbf{m}_{0})}^{\mathbf{E}(\mathbf{m}_{4})}\dfrac{1}{f((u-c)_{+})+\epsilon}\,du$
$\displaystyle\quad+\frac{1}{2}\left(I(2\mathbf{m}_{4}^{+})+I(2\mathbf{m}_{4}^{-})\right)-\frac{1}{2}\left(I(2\mathbf{m}_{0}^{+})+I(2\mathbf{m}_{0}^{-})\right)$
$\displaystyle\leqslant\beta\left(\mathbf{g}_{\epsilon}(\mathbf{m}_{4})-\mathbf{g}_{\epsilon}(\mathbf{m}_{0})\right)=\beta\Delta\mathbf{g}_{\epsilon}.$

In other words, the critical height of the free energy in the modified
landscape is bounded above by $\beta$ times the critical height of the free
energy in the original landscape.

A direct application of (Mathieu and Picco, 1998, Theorem $2.7$) yields the
following result on the asymptotics of the spectral gap:

######  Theorem 3.2 (Asymptotics of the spectral gap).

Suppose $\theta>0$, $\beta>\cosh^{2}(\beta\theta)$ are fixed, and
$\mathbf{m}_{0}$ is the saddle point while $\mathbf{m}_{1},\mathbf{m}_{2}$ are
the two global minima on the original free energy landscape
$\mathbf{g}_{\epsilon}$. For
$c\in[\mathbf{E}(\mathbf{m}_{1}),\mathbf{E}(\mathbf{m}_{0})]$, we have

$\displaystyle\lim_{N\to\infty}\dfrac{1}{N}\log\lambda_{2}(-\mathbf{M}^{f}_{\epsilon,c,N})$
$\displaystyle=-\Delta\mathbf{g}^{f}_{\epsilon,c}\geqslant-\beta\Delta\mathbf{g}_{\epsilon}=\lim_{N\to\infty}\dfrac{1}{N}\log\lambda_{2}(-\mathbf{M}^{0}_{\epsilon,N}).$

In essence, the relaxation time in the mean-field limit of the transformed
generator $\mathbf{M}^{f}_{\epsilon,c,N}$ is asymptotically less than or equal
to that of the original generator $\mathbf{M}^{0}_{\epsilon,N}$.

##  4\. Discrete simulated annealing with landscape modification

In previous sections of this paper, the temperature parameter is fixed. In
this section, we consider the non-homogeneous Metropolis-Hastings with
landscape modification where the temperature schedule
$(\epsilon_{t})_{t\geqslant 0}$ is time-dependent, non-increasing and goes to
zero as $t\to\infty$.

We first introduce the notion of clipped critical height $c^{*}$. Recall that
in (2.4) we introduce $H^{f}_{\epsilon,c}$ and $H^{0}$ as the critical height
for $M^{f}_{\epsilon,c}$ and $M^{0}_{\epsilon}$ respectively. It turns out
that these critical heights are closely related to $c^{*}$:

(4.1) $\displaystyle c^{*}:=\max_{x,y\in\mathcal{X}}\\{G^{0}(x,y)\wedge
c-\mathcal{H}(x)\wedge c-\mathcal{H}(y)\wedge c+\min\mathcal{H}\\},$

where we recall $G^{0}(x,y)$, the lowest possible maximum elevation between
$x$ and $y$, is defined in (2.3). One can understand $c^{*}$ as if the
Hamiltonian function is $\mathcal{H}\wedge c$.

Our first result gives the asymptotic order of the spectral gap
$\lambda_{2}(-M^{f}_{\epsilon,c})$ in terms of $c^{*}$ in the low temperature
regime, which will be proven to be essential in obtaining convergence result
for simulated annealing:

######  Theorem 4.1.

Assume that $f$ and $\min\mathcal{H}\leqslant c\leqslant\max\mathcal{H}$
satisfy Assumption 2.1, and in addition for small enough $x>0$ we have
$f(x)\geqslant x$. There exists positive constants $C_{2},C_{3},C_{4}$ that
depend on the state space $\mathcal{X}$ and the proposal generator $Q$ but not
on the temperature $\epsilon$, and subexponential function

$C_{1}(\beta):=\begin{cases}\frac{1}{C_{2}}\left(1+\beta(\max\mathcal{H}-c)\right)\exp\bigg{\\{}\frac{1}{f(\delta)}\left(\max\mathcal{H}-\min\mathcal{H}\right)\bigg{\\}},&\mbox{if
}c<\max\mathcal{H};\\\ \frac{1}{C_{2}},&\mbox{if
}c=\max\mathcal{H},\end{cases}$

where $\delta:=\min_{x;~{}\mathcal{H}(x)>c}\\{\mathcal{H}(x)-c\\}$, such that

$\displaystyle C_{1}^{-1}(\beta)e^{-\beta c^{*}}\leqslant
C_{2}e^{-H^{f}_{\epsilon,c}}\leqslant\lambda_{2}(-M^{f}_{\epsilon,c})\leqslant
C_{3}e^{-H^{f}_{\epsilon,c}}\leqslant C_{4}e^{-\beta c^{*}},$

where $H^{f}_{\epsilon,c}$ is introduced in (2.4) and $c^{*}$ is defined in
(4.1). Consequently, this leads to

$\displaystyle\lim_{\beta\to\infty}\dfrac{1}{\beta}\log\lambda_{2}(-M^{f}_{\epsilon,c})=-c^{*},$

As a corollary of the above result Theorem 4.1, using the asymptotics of the
spectral gap we derive similar asymptotics of the mixing time and tunneling
time:

######  Corollary 4.1 (Asymptotics of mixing and tunneling times in the low-
temperature regime).

Assume the same setting as in Theorem 4.1. Let
$S_{min}:=\arg\min\mathcal{H}(x)$ be the set of global minima of
$\mathcal{H}$, $\eta\in S_{min}$ and $\sigma,\eta$ attain $H^{0}$ such that
$H^{0}=G^{0}(\sigma,\eta)-\mathcal{H}(\sigma)$. Then the following statements
hold:

  1. (1)

$\lim_{\beta\to\infty}\dfrac{1}{\beta}\log
t_{mix}(M^{f}_{\epsilon,c},1/4)=c^{*}.$

  2. (2)

$\lim_{\beta\to\infty}\dfrac{1}{\beta}\log\mathbb{E}_{\sigma}(\tau^{f}_{\eta})=c^{*}\leqslant
H^{0}=\lim_{\beta\to\infty}\dfrac{1}{\beta}\log\mathbb{E}_{\sigma}(\tau^{0}_{\eta}).$

In particular, when $c=\mathcal{H}_{min}$, we have subexponential tunneling
time as
$\lim_{\beta\to\infty}\dfrac{1}{\beta}\log\mathbb{E}_{\sigma}(\tau^{f}_{\eta})=0=c^{*}$.

Note that in the case where both $\sigma,\eta\in S_{min}$ with initial state
$\sigma$, it is a reasonable choice to pick the parameter
$c=\mathcal{H}(X^{f}(0))=\mathcal{H}(\sigma)=\mathcal{H}_{min}$, and in this
setting we have subexponential tunneling time on the modified landscape. For
example, in the Widom-Rowlinson model with $m\in\mathbb{N}$ particle types,
$S_{min}$ is precisely the set of configurations in which all sites are
occupied by particles of the same type. We refer interested readers to Nardi
and Zocca (2019); Zocca (2018) for recent work on the energy landscape
analysis of various statistical physics models in this direction.

To prove convergence result for simulated annealing with landscape
modification, as our target function $\mathcal{H}^{f}_{\epsilon,c}$ depends on
time through the cooling schedule, we are in the setting of simulated
annealing with time-dependent energy function as in Löwe (1996). We first
present the following auxillary lemma, where we verify various assumptions in
Löwe (1996) in our setting. We also decide to put it in this section rather
than in the proof since it will help to better understand the convergence
result in Theorem 4.2 below.

######  Lemma 4.1.

Assume the same setting as in Theorem 4.1. Let
$M:=\max\mathcal{H}-\min\mathcal{H}$, and the cooling schedule is, for
arbitrary $\epsilon$ such that $M+\max\mathcal{H}-c>\epsilon>0$ and
$t\geqslant 0$,

$\epsilon_{t}=\dfrac{c^{*}+\epsilon}{\ln(t+1)}.$

We have

  1. (1)

For all $x\in\mathcal{X}$ and all $t\geqslant 0$,

$0\leqslant\epsilon_{t}\mathcal{H}^{f}_{\epsilon_{t},c}(x)\leqslant M.$

  2. (2)

For all $x\in\mathcal{X}$,

$\left|\dfrac{\partial}{\partial
t}\epsilon_{t}\mathcal{H}^{f}_{\epsilon_{t},c}(x)\right|\leqslant\dfrac{2M}{(\ln(1+t))(1+t)}.$

  3. (3)

Let $R_{t}:=\sup_{x}\frac{\partial}{\partial
t}\epsilon_{t}\mathcal{H}^{f}_{\epsilon_{t},c}(x)$ and
$B:=6M/(c^{*}+\epsilon)$. For all $t\geqslant 0$,

$\beta_{t}^{\prime}M+\beta_{t}R_{t}\leqslant\dfrac{3M}{(c^{*}+\epsilon)(1+t)}=\dfrac{B}{2(1+t)}.$

  4. (4)

Let

$p:=\dfrac{2M}{M+\max\mathcal{H}-\epsilon-c}>2,$

and

$A:=\begin{cases}\dfrac{1}{C_{2}(\min_{x}\mu(x))^{(p-2)/p}}\exp\bigg{\\{}\frac{1}{f(\delta)}\left(\max\mathcal{H}-\min\mathcal{H}\right)\bigg{\\}},&\mbox{if
}c<\max\mathcal{H};\\\ \dfrac{1}{C_{2}(\min_{x}\mu(x))^{(p-2)/p}},&\mbox{if
}c=\max\mathcal{H},\end{cases}$

where $C_{2},\delta$ are as in Theorem 4.1 and we recall that $\mu$ is the
stationary measure of the proposal generator $Q$. For
$g\in\ell^{p}(\pi_{\epsilon_{t},c}^{f})$, we have

$\left\lVert
g-\pi_{\epsilon_{t},c}^{f}(g)\right\rVert_{\ell^{p}(\pi^{f}_{\epsilon_{t},c})}^{2}\leqslant
A(1+t)\langle-M^{f}_{\epsilon_{t},c}g,g\rangle_{\pi^{f}_{\epsilon_{t},c}}.$

With the above Lemma and the notations introduced there, we are ready to give
one of the main results of this paper concerning the large-time convergence of
discrete simulated annealing with landscape modification. In a nutshell, we
can operate a faster logarithmic cooling schedule with clipped critical height
$c^{*}$, while in classical simulated annealing the critical height is
$H^{0}$. This result is analogous to the result that we have obtained in Choi
(2020) for improved kinetic simulated annealing.

######  Theorem 4.2.

Assume the same setting as in Theorem 4.1. Let $A,B,p$ be the quantities as
introduced in Lemma 4.1. Define

$\displaystyle\overline{\epsilon}$ $\displaystyle:=\dfrac{p-2}{p},\quad
K:=\dfrac{4(1+2AB)}{1-\exp\\{-\frac{1}{2A}-B\\}},\quad
S_{min}:=\arg\min\mathcal{H},\quad\underline{d}:=\min_{x;~{}\mathcal{H}(x)\neq\mathcal{H}_{min}}\mathcal{H}(x).$

Under the cooling schedule of the form, for any $\epsilon>0$ as in Lemma 4.1,

$\epsilon_{t}=\dfrac{c^{*}+\epsilon}{\ln(t+1)},$

we then have, for any $x\in\mathcal{X}\backslash S_{min}$ and $t\geqslant
e^{1/\overline{\epsilon}}-1$,

$\mathbb{P}_{x}\left(\tau^{f}_{S_{min}}>t\right)\leqslant(1+K^{\frac{1}{2\overline{\epsilon}}})\sqrt{\pi^{f}_{\epsilon_{t},c}(\mathcal{X}\backslash
S_{min})}+\pi^{f}_{\epsilon_{t},c}(\mathcal{X}\backslash S_{min})\to
0\quad\text{as }t\to\infty.$

Note that

$\displaystyle\pi^{f}_{\epsilon_{t},c}(\mathcal{X}\backslash S_{min})$
$\displaystyle\leqslant\begin{cases}\dfrac{1}{\mu(S_{min})}e^{-\beta_{t}(\underline{d}-\mathcal{H}_{min})},&\mbox{if
}c\geqslant\underline{d};\\\
\dfrac{1}{\mu(S_{min})}\exp\bigg{\\{}-\int_{c}^{\underline{d}}\frac{1}{f(u-c)+\epsilon_{t}}du\bigg{\\}},&\mbox{if
}\mathcal{H}_{min}\leqslant c<\underline{d}.\end{cases}$

The rest of this section is devoted to the proofs of Theorem 4.1, Corollary
4.1, Lemma 4.1 and Theorem 4.2.

###  4.1. Proof of Theorem 4.1

First, using the classical result by Holley and Stroock (1988), it is
immediate that

$\displaystyle
C_{2}e^{-H^{f}_{\epsilon,c}}\leqslant\lambda_{2}(-M^{f}_{\epsilon,c})\leqslant
C_{3}e^{-H^{f}_{\epsilon,c}}.$

For any arbitrary
$x_{1},x_{2}\in\\{\mathcal{H}(x_{1})\geqslant\mathcal{H}(x_{2})\\}$, we deduce
the following upper bound:

$\displaystyle\mathcal{H}^{f}_{\epsilon,c}(x_{1})-\mathcal{H}^{f}_{\epsilon,c}(x_{2})$
$\displaystyle=\int_{\mathcal{H}(x_{2})}^{\mathcal{H}(x_{1})}\dfrac{1}{f((u-c)_{+})+\epsilon}\,du$
$\displaystyle=\begin{cases}\beta(\mathcal{H}(x_{1})-\mathcal{H}(x_{2})),&\mbox{if
}c\geqslant\mathcal{H}(x_{1})>\mathcal{H}(x_{2});\\\
\beta(c-\mathcal{H}(x_{2}))+\int_{c}^{\mathcal{H}(x_{1})}\frac{1}{f(u-c)+\epsilon}\,du,&\mbox{if
}\mathcal{H}(x_{1})>c\geqslant\mathcal{H}(x_{2});\\\
\int_{\mathcal{H}(x_{2})}^{\mathcal{H}(x_{1})}\frac{1}{f(u-c)+\epsilon}\,du,&\mbox{if
}\mathcal{H}(x_{1})>\mathcal{H}(x_{2})>c.\end{cases}$
$\displaystyle\leqslant\begin{cases}\beta(\mathcal{H}(x_{1})\wedge
c-\mathcal{H}(x_{2})\wedge c),&\mbox{if
}c\geqslant\mathcal{H}(x_{1})>\mathcal{H}(x_{2});\\\
\beta(\mathcal{H}(x_{1})\wedge c-\mathcal{H}(x_{2})\wedge
c)+\ln(1+\beta(\max\mathcal{H}-c)),&\mbox{if
}\mathcal{H}(x_{1})>c\geqslant\mathcal{H}(x_{2});\\\
\frac{1}{f(\delta)}\left(\max\mathcal{H}-\min\mathcal{H}\right),&\mbox{if
}\mathcal{H}(x_{1})>\mathcal{H}(x_{2})>c,.\end{cases}$

As a result, $C_{2}^{-1}e^{H^{f}_{\epsilon,c}}\leqslant e^{\beta
c^{*}}C_{1}(\beta)$. On the other hand, we have the following lower bound:

$\displaystyle\mathcal{H}^{f}_{\epsilon,c}(x_{1})-\mathcal{H}^{f}_{\epsilon,c}(x_{2})$
$\displaystyle\geqslant\begin{cases}\beta(\mathcal{H}(x_{1})\wedge
c-\mathcal{H}(x_{2})\wedge c),&\mbox{if
}c\geqslant\mathcal{H}(x_{1})>\mathcal{H}(x_{2});\\\
\beta(\mathcal{H}(x_{1})\wedge c-\mathcal{H}(x_{2})\wedge c),&\mbox{if
}\mathcal{H}(x_{1})>c\geqslant\mathcal{H}(x_{2});\\\
\frac{1}{f(\mathcal{H}(x_{1})-c)}\left(\mathcal{H}(x_{1})-\mathcal{H}(x_{2})\right),&\mbox{if
}\mathcal{H}(x_{1})>\mathcal{H}(x_{2})>c,\end{cases}$

and hence $e^{H^{f}_{\epsilon,c}}\geqslant e^{\beta c^{*}}C_{4}^{-1}$.

###  4.2. Proof of Corollary 4.1

We first prove item (1). For continuous-time reversible Markov chain, by
(Levin and Peres, 2017, Theorem $12.5$, $20.6$) we bound the total variation
mixing time by relaxation time via

$\dfrac{1}{\lambda_{2}(-M^{f}_{\epsilon,c})}\log 2\leqslant
t_{mix}(M^{f}_{\epsilon,c},1/4)\leqslant\dfrac{1}{\lambda_{2}(-M^{f}_{\epsilon,c})}\log\left(\dfrac{4}{\pi^{f}_{min}}\right),$

where
$\pi_{min}^{f}:=\min_{x}\pi^{f}_{\epsilon,c}(x)=\dfrac{\mu(x^{*})}{Z^{f}_{\epsilon,c}},$
for some $x^{*}\in S_{min}$ and
$Z^{f}_{\epsilon,c}:=\sum_{x\in\mathcal{X}}e^{-\mathcal{H}_{\epsilon,c}^{f}(x)}\mu(x)$
is the normalization constant. Note that since $\ln
Z^{f}_{\epsilon,c}\to\ln\mu(S_{min})$ and so

$\lim_{\beta\to\infty}\dfrac{\ln Z^{f}_{\epsilon,c}}{\beta}=0.$

Item (1) follows by collecting the above results together with Theorem 4.1.

Next, we prove item (2). First, using the random target lemma (Levin and
Peres, 2017, Lemma $12.17$), we have

$\pi^{f}_{\epsilon,c}(\eta)\mathbb{E}_{\sigma}(\tau^{f}_{\eta})\leqslant\sum_{x\in\mathcal{X}}\pi^{f}_{\epsilon,c}(x)\mathbb{E}_{\sigma}(\tau^{f}_{x})\leqslant(|\mathcal{X}|-1)\dfrac{1}{\lambda_{2}(-M^{f}_{\epsilon,c})}.$

Since $\mathcal{H}(\eta)=0$ and $Z^{f}_{\epsilon,c}\leqslant 1$, upon
rearranging and using Theorem 4.1 yields

$\limsup_{\beta\to\infty}\dfrac{1}{\beta}\log\mathbb{E}_{\sigma}(\tau^{f}_{\eta})\leqslant\lim_{\beta\to\infty}\dfrac{1}{\beta}\log\dfrac{1}{\lambda_{2}(-M^{f}_{\epsilon,c})}=c^{*}.$

Define the equilibrium potential and capacity of the pair $(\sigma,\eta)$ as
in (Bovier and den Hollander, 2015, Chapter $7.2$) to be respectively

$\displaystyle h_{\sigma,\eta}^{f}(x)$
$\displaystyle:=\mathbb{P}_{x}(\tau^{f}_{\sigma}<\tau^{f}_{\eta}),$
$\displaystyle\mathrm{cap}^{M^{f}_{\epsilon,c}}(\sigma,\eta)$
$\displaystyle:=\inf_{f:f|_{A}=1,f|_{B}=0}\langle-M^{f}_{\epsilon,c}f,f\rangle_{\pi^{f}_{\epsilon,c}}=\langle-M^{f}_{\epsilon,c}h_{\sigma,\eta}^{f},h_{\sigma,\eta}^{f}\rangle_{\pi^{f}_{\epsilon,c}}.$

If we prove that

(4.2)
$\displaystyle\mathrm{cap}^{M^{f}_{\epsilon,c}}(\sigma,\eta)\leqslant\dfrac{1}{Z^{f}_{\epsilon,c}}\left(\sum_{x,y}\mu(x)Q(x,y)\right)e^{-\beta
G^{0}(\sigma,\eta)},$

then together the mean hitting time formula with equilibrium potential and
capacity leads to

$\displaystyle\mathbb{E}_{\sigma}(\tau^{f}_{\eta})$
$\displaystyle=\dfrac{1}{\mathrm{cap}^{M^{f}_{\epsilon,c}}(\sigma,\eta)}\sum_{y\in\mathcal{X}}\pi_{\epsilon,c}^{f}(y)h_{\sigma,\eta}^{f}(y)$
$\displaystyle\geqslant\dfrac{1}{\mathrm{cap}^{M^{f}_{\epsilon,c}}(\sigma,\eta)}\pi_{\epsilon,c}^{f}(\sigma)h_{\sigma,\eta}^{f}(\sigma)\geqslant\dfrac{\mu(\sigma)}{\sum_{x,y}\mu(x)Q(x,y)}e^{\beta
c^{*}},$

and the desired result follows since

$\liminf_{\beta\to\infty}\dfrac{1}{\beta}\log\mathbb{E}_{\sigma}(\tau^{f}_{\eta})\geqslant
c^{*}.$

It therefore remains to prove (4.2). Define

$\Phi(\sigma,\eta):=\\{x\in\mathcal{X};~{}G^{0}(x,\sigma)\leqslant
G^{0}(x,\eta)\\}.$

Writing $\mathbf{1}_{A}$ to be the indicator function of the set $A$, the
Dirichlet principle of capacity gives

$\displaystyle\mathrm{cap}^{M^{f}_{\epsilon,c}}(\sigma,\eta)\leqslant\langle-M^{f}_{\epsilon,c}\mathbf{1}_{\Phi(\sigma,\eta)},\mathbf{1}_{\Phi(\sigma,\eta)}\rangle_{\pi^{f}_{\epsilon,c}}$
$\displaystyle=\dfrac{1}{Z^{f}_{\epsilon,c}}\sum_{x\in\Phi(\sigma,\eta),y\notin\Phi(\sigma,\eta)}e^{-\beta\left(H(x)\vee
H(y)\right)}\mu(x)Q(x,y)$
$\displaystyle\leqslant\dfrac{1}{Z^{f}_{\epsilon,c}}\left(\sum_{x,y}\mu(x)Q(x,y)\right)e^{-\beta
G^{0}(\sigma,\eta)}.$

where in the last inequality we use the fact that $G^{0}(\sigma,\eta)$ is the
lowest possible highest elevation between $\sigma$ and $\eta$.

###  4.3. Proof of Lemma 4.1

We first prove item (1). The lower bound is immediate, while the upper bound
can be deduced via

$\epsilon_{t}\mathcal{H}^{f}_{\epsilon_{t},c}\leqslant\epsilon_{t}\int_{\mathcal{H}_{min}}^{\mathcal{H}(x)}\dfrac{1}{\epsilon_{t}}\,du\leqslant
M.$

Next, we prove item (2). We consider

$\displaystyle\dfrac{\partial}{\partial
t}\epsilon_{t}\mathcal{H}^{f}_{\epsilon_{t},c}(x)$
$\displaystyle=\mathcal{H}^{f}_{\epsilon_{t},c}(x)\left(\dfrac{\partial}{\partial
t}\epsilon_{t}\right)+\epsilon_{t}\dfrac{\partial}{\partial
t}\mathcal{H}^{f}_{\epsilon_{t},c}(x)$
$\displaystyle=\mathcal{H}^{f}_{\epsilon_{t},c}(x)\dfrac{-c^{*}-\epsilon}{(\ln(t+1))^{2}}\dfrac{1}{t+1}+\epsilon_{t}\epsilon_{t}^{\prime}\int_{\mathcal{H}_{min}}^{\mathcal{H}(x)}-\dfrac{1}{(f((u-c)_{+})+\epsilon_{t})^{2}}\,du.$

This leads to

$\displaystyle\left|\dfrac{\partial}{\partial
t}\epsilon_{t}\mathcal{H}^{f}_{\epsilon_{t},c}(x)\right|\leqslant\dfrac{2M}{(\ln(t+1))(t+1)}.$

Thirdly, we prove item (3), and using item (2) we calculate that

$\displaystyle\beta_{t}^{\prime}M+\beta_{t}R_{t}$
$\displaystyle\leqslant\dfrac{M}{(c^{*}+\epsilon)(t+1)}+\dfrac{2M}{(c^{*}+\epsilon)(1+t)}=\dfrac{3M}{(c^{*}+\epsilon)(1+t)}.$

Finally, we prove item (4). Following exactly the same calculation as in the
proof of (Löwe, 1996, Lemma $3.5$), we see that

$\displaystyle\left\lVert
g-\pi_{\epsilon_{t},c}^{f}(g)\right\rVert_{\ell^{p}(\pi^{f}_{\epsilon_{t},c})}^{2}$
$\displaystyle\leqslant
A\left(1+\beta_{t}(\max\mathcal{H}-c)\right)e^{\beta_{t}(c^{*}+M\frac{p-2}{p})}\langle-M^{f}_{\epsilon_{t},c}g,g\rangle_{\pi^{f}_{\epsilon_{t},c}}$
$\displaystyle\leqslant
Ae^{\beta_{t}(c^{*}+M\frac{p-2}{p}+\max\mathcal{H}-c)}\langle-M^{f}_{\epsilon_{t},c}g,g\rangle_{\pi^{f}_{\epsilon_{t},c}}.$

The desired result follows if we let

$\epsilon=\dfrac{M(p-2)}{p}+\max\mathcal{H}-c$

so that

$p=\dfrac{2M}{M+\max\mathcal{H}-\epsilon-c}.$

###  4.4. Proof of Theorem 4.2

We would like to invoke the results in Löwe (1996) for time-dependent target
function in simulated annealing. In Lemma 4.1 item (1), (2), (3) and (4), we
verify that equation $(11)$, $(12)$ and Assumption $(A1)$, $(A2)$ respectively
hold in Löwe (1996). Consequently, if we let
$h_{t}(y):=\mathbb{P}_{x}(X^{f}_{\epsilon,c}(t)=y)/\pi^{f}_{\epsilon,c}(y)$,
then according to (Holley and Stroock, 1988, Lemma $1.7$), its $\ell^{2}$ norm
is bounded by

$\left\lVert h_{t}\right\rVert_{\ell^{2}(\pi^{f}_{\epsilon_{t},c})}\leqslant
1+K^{\frac{1}{2\overline{\epsilon}}},$

for $t\geqslant e^{1/\overline{\epsilon}}-1$. The desired result follows from
exactly the same argument as in (Löwe, 1996, Theorem $3.8$).

Now, we calculate $\pi^{f}_{\epsilon_{t},c}(\mathcal{X}\backslash S_{min})$.
For $c\geqslant\underline{d}$, we compute that

$\displaystyle\pi^{f}_{\epsilon_{t},c}(\mathcal{X}\backslash S_{min})$
$\displaystyle=\dfrac{\sum_{x\in\mathcal{X}\backslash
S_{min}}e^{-\mathcal{H}_{\epsilon_{t},c}^{f}(x)}\mu(x)}{\sum_{x\in\mathcal{X}}e^{-\mathcal{H}_{\epsilon_{t},c}^{f}(x)}\mu(x)}$
$\displaystyle\leqslant\dfrac{\sum_{x;~{}\mathcal{H}(x)\geqslant\underline{d}}\mu(x)}{\sum_{x;\mathcal{H}(x)\leqslant\underline{d}}\exp\\{\int_{\mathcal{H}(x)}^{d}\frac{1}{\epsilon_{t}}\,du\\}\mu(x)}$
$\displaystyle\leqslant
e^{-\beta_{t}(\underline{d}-\mathcal{H}_{min})}\dfrac{1}{\mu(S_{min})}.$

On the other hand, for $\mathcal{H}_{min}\leqslant c<\underline{d}$,

$\displaystyle\pi^{f}_{\epsilon_{t},c}(\mathcal{X}\backslash S_{min})$
$\displaystyle=\dfrac{\sum_{x\in\mathcal{X}\backslash
S_{min}}e^{-\mathcal{H}_{\epsilon_{t},c}^{f}(x)}\mu(x)}{\sum_{x\in\mathcal{X}}e^{-\mathcal{H}_{\epsilon_{t},c}^{f}(x)}\mu(x)}$
$\displaystyle\leqslant\dfrac{1}{\mu(S_{min})}\exp\bigg{\\{}-\int_{\mathcal{H}_{min}}^{\underline{d}}\dfrac{1}{f((u-c)_{+})+\epsilon_{t}}du\bigg{\\}}$
$\displaystyle\leqslant\dfrac{1}{\mu(S_{min})}\exp\bigg{\\{}-\int_{c}^{\underline{d}}\dfrac{1}{f(u-c)+\epsilon_{t}}du\bigg{\\}}.$

##  5\. Connections between landscape modification and …

In this section, we outline similarities and differences in idea between
Metropolis-Hastings (MH) with landscape modification and other common
acceleration techniques in the literature for MH and simulated annealing.

###  5.1. Catoni’s energy transformation algorithm

Let $\alpha_{1}\geqslant 0,\alpha_{2}\geqslant
0,\alpha_{3}>-\mathcal{H}_{min}$ be three parameters. In Catoni (1998, 1996),
the author introduces the energy transformation algorithm by transforming the
Hamiltonian $\mathcal{H}$ to

$F_{\alpha_{1},\alpha_{2},\alpha_{3}}(x):=\alpha_{1}\mathcal{H}(x)+\alpha_{2}\log\left(\mathcal{H}(x)+\alpha_{3}\right).$

Recall that in Section 2.1, MH with landscape modification can be considered
as a state-dependent version of energy transformation if we take $f(x)=x$,
$\alpha_{3}=-c+\epsilon$ and $\alpha_{1}$, $\alpha_{2}$ are chosen in a state-
dependent manner:

$\alpha_{1}(x)=\mathbf{1}_{\\{\mathcal{H}(x)\leqslant
c\\}},\quad\alpha_{2}(x)=\mathbf{1}_{\\{\mathcal{H}(x)>c\\}}.$

Note that MH with landscape modification can give rise to other kinds of
energy transformation by different choices of $f$, see for example the
quadratic case or the square root case in Section 2.2 and 2.3 respectively.
Another remark is that the idea of mapping the function from $\mathcal{H}$ to
$F(\mathcal{H})$ with $F$ being strictly increasing and concave can be dated
back to R. Azencott.

###  5.2. preconditioning of the Hamiltonian

Landscape modification can be understood as a state-dependent preconditioning
of the Hamiltonian $\mathcal{H}$. Recall that in (2.6) we compute the
acceptance-rejection probability in MH by

$\displaystyle\exp\left(-(\mathcal{H}_{\epsilon,c}^{f}(y)-\mathcal{H}_{\epsilon,c}^{f}(x))_{+}\right)$
$\displaystyle=\begin{cases}1,&\mbox{if
}\mathcal{H}(y)\leqslant\mathcal{H}(x);\\\
\exp\left(-\beta(\mathcal{H}(y)-\mathcal{H}(x))\right),&\mbox{if
}c\geqslant\mathcal{H}(y)>\mathcal{H}(x);\\\
\exp\left(-\beta(c-\mathcal{H}(x))-\int_{c}^{\mathcal{H}(y)}\frac{1}{f(u-c)+\epsilon}\,du\right),&\mbox{if
}\mathcal{H}(y)>c\geqslant\mathcal{H}(x);\\\
\exp\left(-\int_{\mathcal{H}(x)}^{\mathcal{H}(y)}\frac{1}{f(u-c)+\epsilon}\,du\right),&\mbox{if
}\mathcal{H}(y)>\mathcal{H}(x)>c.\end{cases}$

On the set $\\{c\geqslant\mathcal{H}(y)>\mathcal{H}(x)\\}$, the acceptance-
rejection probability is the same as the original MH, while on the set
$\\{\mathcal{H}(y)>c\geqslant\mathcal{H}(x)\\}$ and
$\\{\mathcal{H}(y)>\mathcal{H}(x)>c\\}$, the acceptance-rejection probability
is higher than that of the original MH. Therefore, there is a higher chance of
moving to other states when the algorithm is above the threshold $c$.

###  5.3. importance sampling

In importance sampling, the target distribution is altered for possible
benefits and speedups such as variance reduction. In landscape modification,
the target distribution in MH is altered from the original Gibbs distribution
$\pi^{0}(x)\propto e^{-\beta\mathcal{H}(x)}$ to
$\pi^{f}_{\epsilon,c}(x)\propto e^{-\mathcal{H}_{\epsilon,c}^{f}(x)}$, while
the set of stationary points is preserved in the sense that $\mathcal{H}$ and
$\mathcal{H}^{f}_{\epsilon,c}$ share the same set of stationary points. In
importance sampling however, the set of stationary points need not be
preserved between the altered function and the original function.

###  5.4. quantum annealing

In quantum annealing Wang et al. (2016), given a target Hamiltonian
$\mathcal{H}$ and an initial Hamiltonian $\mathcal{H}_{init}$ that is usually
easy to optimize, we optimize a time-dependent function $Q_{t}$ defined by,
for $t\in[0,T]$,

$Q_{t}(x):=A(t)\mathcal{H}_{init}(x)+B(t)\mathcal{H}(x),$

where $A(t)$ and $B(t)$ are smooth annealing schedules that satisfy
$A(T)=B(0)=0$ and $T$ is the total annealing time. We also choose $A(t)$ to be
decreasing and $B(t)$ to be increasing on the interval $[0,T]$.

In simulated annealing with landscape modification, we also optimize a time-
dependent function $\mathcal{H}^{f}_{\epsilon_{t},c}$ which shares the same
set of stationary points as the target $\mathcal{H}$. In quantum annealing,
$\mathcal{H}_{init}$ and $\mathcal{H}$ do not necessarily share the same set
of stationary points. We mention the work Del Moral and Miclo (1999); Löwe
(1996); Frigerio and Grillo (1993) for simulated annealing with time-dependent
energy function.

## Acknowledgements

We thank Laurent Miclo for pointers to the work of Olivier Catoni. The author
acknowledges the support from The Chinese University of Hong Kong, Shenzhen
grant PF01001143, the financial support from AIRS - Shenzhen Institute of
Artificial Intelligence and Robotics for Society Project 2019-INT002 and NSFC
Project number 12001460.

## References

  * Bovier and den Hollander (2015) A. Bovier and F. den Hollander.  _Metastability_ , volume 351 of _Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]_.  Springer, Cham, 2015.  A potential-theoretic approach.
  * Catoni (1996) O. Catoni.  Metropolis, simulated annealing, and iterated energy transformation algorithms: theory and experiments.  volume 12, pages 595–623. 1996.  Special issue for the Foundations of Computational Mathematics Conference (Rio de Janeiro, 1997).
  * Catoni (1998) O. Catoni.  The energy transformation method for the Metropolis algorithm compared with simulated annealing.  _Probab. Theory Related Fields_ , 110(1):69–89, 1998.
  * Choi (2020) M. C. Choi.  On the convergence of an improved and adaptive kinetic simulated annealing.  _arXiv preprint arXiv:2009.00195_ , 2020.
  * Del Moral and Miclo (1999) P. Del Moral and L. Miclo.  On the convergence and applications of generalized simulated annealing.  _SIAM J. Control Optim._ , 37(4):1222–1250, 1999\.
  * Deuschel and Mazza (1994) J.-D. Deuschel and C. Mazza.  $L^{2}$ convergence of time nonhomogeneous Markov processes. I. Spectral estimates.  _Ann. Appl. Probab._ , 4(4):1012–1056, 1994.
  * Fang et al. (1997) H. Fang, M. Qian, and G. Gong.  An improved annealing method and its large-time behavior.  _Stochastic Process. Appl._ , 71(1):55–74, 1997\.
  * Frigerio and Grillo (1993) A. Frigerio and G. Grillo.  Simulated annealing with time-dependent energy function.  _Math. Z._ , 213(1):97–116, 1993.
  * Holley and Stroock (1988) R. Holley and D. Stroock.  Simulated annealing via Sobolev inequalities.  _Comm. Math. Phys._ , 115(4):553–569, 1988.
  * Levin and Peres (2017) D. A. Levin and Y. Peres.  _Markov chains and mixing times_.  American Mathematical Society, Providence, RI, 2017.
  * Löwe (1996) M. Löwe.  Simulated annealing with time-dependent energy function via Sobolev inequalities.  _Stochastic Process. Appl._ , 63(2):221–233, 1996\.
  * Mathieu and Picco (1998) P. Mathieu and P. Picco.  Metastability and convergence to equilibrium for the random field Curie-Weiss model.  _J. Statist. Phys._ , 91(3-4):679–732, 1998.
  * Nardi and Zocca (2019) F. R. Nardi and A. Zocca.  Tunneling behavior of Ising and Potts models in the low-temperature regime.  _Stochastic Process. Appl._ , 129(11):4556–4575, 2019.
  * Wang et al. (2016) Y. Wang, S. Wu, and J. Zou.  Quantum annealing with Markov chain Monte Carlo simulations and D-wave quantum computers.  _Statist. Sci._ , 31(3):362–398, 2016.
  * Zocca (2018) A. Zocca.  Low-temperature behavior of the multicomponent Widom-Rowlison model on finite square lattices.  _J. Stat. Phys._ , 171(1):1–37, 2018.