Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: An improved variant of simulated annealing that converges under fast
  cooling   Given a target function $U$ to minimize on a finite state space
$\mathcal{X}$, a proposal chain with generator $Q$ and a cooling schedule
$T(t)$ that depends on time $t$, in this paper we study two types of simulated
annealing (SA) algorithms with generators $M_{1,t}(Q,U,T(t))$ and
$M_{2,t}(Q,U,T(t))$ respectively. While $M_{1,t}$ is the classical SA
algorithm, we introduce a simple and improved variant that we call $M_{2,t}$
which provably converges faster. When $T(t) > c_{M_2}/\log(t+1)$ follows the
logarithmic cooling schedule, our proposed algorithm is strongly ergodic both
in total variation and in relative entropy, and converges to the set of global
minima, where $c_{M_2}$ is a constant that we explicitly identify. If $c_{M_1}$
is the optimal hill-climbing constant that appears in logarithmic cooling of
$M_{1,t}$, we show that $c_{M_1} \geq c_{M_2}$ and give simple conditions under
which $c_{M_1} > c_{M_2}$. Our proposed $M_{2,t}$ thus converges under a faster
logarithmic cooling in this regime. The other situation that we investigate
corresponds to $c_{M_1} > c_{M_2} = 0$, where we give a class of fast and
non-logarithmic cooling schedule that works for $M_{2,t}$ (but not for
$M_{1,t}$). In addition to these asymptotic convergence results, we compare and
analyze finite-time behaviour between these two annealing algorithms as well.
Finally, we present two algorithms to simulate $M_{2,t}$.

24
The categories of this paper are: dg-ga
29
The categories of this paper are: funct-an
10
The categories of this paper are: q-bio
12
The categories of this paper are: nucl-th
33
The categories of this paper are: plasm-ph
9
The categories of this paper are: nlin
31
The categories of this paper are: ao-sci
37
The categories of this paper are: supr-con
30
The categories of this paper are: q-alg
4
The categories of this paper are: cond-mat
18
The categories of this paper are: econ
1
The categories of this paper are: cs
35
The categories of this paper are: mtrl-th
7
The categories of this paper are: hep-th
22
The categories of this paper are: chao-dyn
14
The categories of this paper are: math-ph