Tail probability estimates of continuous-time simulated annealing processes

We study the convergence rate of a continuous-time simulated annealing process \begin{document}$(X_t; \, t \ge 0)$\end{document} for approximating the global optimum of a given function \begin{document}$f$\end{document}. We prove that the tail probability \begin{document}$\mathbb{P}(f(X_t) > \min f +\delta)$\end{document} decays polynomial in time with an appropriately chosen cooling schedule of temperature, and provide an explicit convergence rate through a non-asymptotic bound. Our argument applies recent development of the Eyring-Kramers law on functional inequalities for the Gibbs measure at low temperatures.

more » « less
Award ID(s):
NSF-PAR ID:
10336723
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Numerical Algebra, Control and Optimization
Volume:
0
Issue:
0
ISSN:
2155-3289
Page Range / eLocation ID:
0
Format(s):
Medium: X
National Science Foundation
##### More Like this
1. Consider the linear transport equation in 1D under an external confining potential \begin{document}$\Phi$\end{document}:

For \begin{document}$\Phi = \frac {x^2}2 + \frac { \varepsilon x^4}2$\end{document} (with \begin{document}$\varepsilon >0$\end{document} small), we prove phase mixing and quantitative decay estimates for \begin{document}${\partial}_t \varphi : = - \Delta^{-1} \int_{ \mathbb{R}} {\partial}_t f \, \mathrm{d} v$\end{document}, with an inverse polynomial decay rate \begin{document}$O({\langle} t{\rangle}^{-2})$\end{document}. In the proof, we develop a commuting vector field approach, suitably adapted to this setting. We will explain why we hope this is relevant for the nonlinear stability of the zero solution for the Vlasov–Poisson system in \begin{document}$1$\end{document}D under the external potential \begin{document}$\Phi$\end{document}.

more » « less
2. Any \begin{document}$C^d$\end{document} conservative map \begin{document}$f$\end{document} of the \begin{document}$d$\end{document}-dimensional unit ball \begin{document}${\mathbb B}^d$\end{document}, \begin{document}$d\geq 2$\end{document}, can be realized by renormalized iteration of a \begin{document}$C^d$\end{document} perturbation of identity: there exists a conservative diffeomorphism of \begin{document}${\mathbb B}^d$\end{document}, arbitrarily close to identity in the \begin{document}$C^d$\end{document} topology, that has a periodic disc on which the return dynamics after a \begin{document}$C^d$\end{document} change of coordinates is exactly \begin{document}$f$\end{document}.

more » « less
3. We consider the well-known Lieb-Liniger (LL) model for \begin{document}$N$\end{document} bosons interacting pairwise on the line via the \begin{document}$\delta$\end{document} potential in the mean-field scaling regime. Assuming suitable asymptotic factorization of the initial wave functions and convergence of the microscopic energy per particle, we show that the time-dependent reduced density matrices of the system converge in trace norm to the pure states given by the solution to the one-dimensional cubic nonlinear Schrödinger equation (NLS) with an explict rate of convergence. In contrast to previous work [3] relying on the formalism of second quantization and coherent states and without an explicit rate, our proof is based on the counting method of Pickl [65,66,67] and Knowles and Pickl [44]. To overcome difficulties stemming from the singularity of the \begin{document}$\delta$\end{document} potential, we introduce a new short-range approximation argument that exploits the Hölder continuity of the \begin{document}$N$\end{document}-body wave function in a single particle variable. By further exploiting the \begin{document}$L^2$\end{document}-subcritical well-posedness theory for the 1D cubic NLS, we can prove mean-field convergence when the limiting solution to the NLS has finite mass, but only for a very special class of \begin{document}$N$\end{document}-body initial states.

more » « less
4. For any finite horizon Sinai billiard map \begin{document}$T$\end{document} on the two-torus, we find \begin{document}$t_*>1$\end{document} such that for each \begin{document}$t\in (0,t_*)$\end{document} there exists a unique equilibrium state \begin{document}$\mu_t$\end{document} for \begin{document}$- t\log J^uT$\end{document}, and \begin{document}$\mu_t$\end{document} is \begin{document}$T$\end{document}-adapted. (In particular, the SRB measure is the unique equilibrium state for \begin{document}$- \log J^uT$\end{document}.) We show that \begin{document}$\mu_t$\end{document} is exponentially mixing for Hölder observables, and the pressure function \begin{document}$P(t) = \sup_\mu \{h_\mu -\int t\log J^uT d \mu\}$\end{document} is analytic on \begin{document}$(0,t_*)$\end{document}. In addition, \begin{document}$P(t)$\end{document} is strictly convex if and only if \begin{document}$\log J^uT$\end{document} is not \begin{document}$\mu_t$\end{document}-a.e. cohomologous to a constant, while, if there exist \begin{document}$t_a\ne t_b$\end{document} with \begin{document}$\mu_{t_a} = \mu_{t_b}$\end{document}, then \begin{document}$P(t)$\end{document} is affine on \begin{document}$(0,t_*)$\end{document}. An additional sparse recurrence condition gives \begin{document}$\lim_{t\downarrow 0} P(t) = P(0)$\end{document}.

more » « less
5. Let \begin{document}$f_c(z) = z^2+c$\end{document} for \begin{document}$c \in {\mathbb C}$\end{document}. We show there exists a uniform upper bound on the number of points in \begin{document}${\mathbb P}^1( {\mathbb C})$\end{document} that can be preperiodic for both \begin{document}$f_{c_1}$\end{document} and \begin{document}$f_{c_2}$\end{document}, for any pair \begin{document}$c_1\not = c_2$\end{document} in \begin{document}${\mathbb C}$\end{document}. The proof combines arithmetic ingredients with complex-analytic: we estimate an adelic energy pairing when the parameters lie in \begin{document}$\overline{\mathbb{Q}}$\end{document}, building on the quantitative arithmetic equidistribution theorem of Favre and Rivera-Letelier, and we use distortion theorems in complex analysis to control the size of the intersection of distinct Julia sets. The proofs are effective, and we provide explicit constants for each of the results.

more » « less