skip to main content

Title: 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.

Award ID(s):
Publication Date:
Journal Name:
Numerical Algebra, Control and Optimization
Page Range or eLocation-ID:
Sponsoring Org:
National Science Foundation
More Like this
  1. 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 finitemore »mass, but only for a very special class of \begin{document}$ N $\end{document}-body initial states.

    « less
  2. 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}.

  3. The disparity in the impact of COVID-19 on minority populations in the United States has been well established in the available data on deaths, case counts, and adverse outcomes. However, critical metrics used by public health officials and epidemiologists, such as a time dependent viral reproductive number (\begin{document}$ R_t $\end{document}), can be hard to calculate from this data especially for individual populations. Furthermore, disparities in the availability of testing, record keeping infrastructure, or government funding in disadvantaged populations can produce incomplete data sets. In this work, we apply ensemble data assimilation techniques which optimally combine model and data to produce a more complete data set providing better estimates of the critical metrics used by public health officials and epidemiologists. We employ a multi-population SEIR (Susceptible, Exposed, Infected and Recovered) model with a time dependent reproductive number and age stratified contact rate matrix for each population. We assimilate the daily death data for populations separated by ethnic/racial groupings using a technique called Ensemble Smoothing with Multiple Data Assimilation (ESMDA) to estimate model parameters and produce an \begin{document}$R_t(n)$\end{document} for the \begin{document}$n^{th}$\end{document} population. We do this with three distinct approaches, (1) using the same contact matrices and prior more »id="M30000">\begin{document}$R_t(n)$\end{document} for each population, (2) assigning contact matrices with increased contact rates for working age and older adults to populations experiencing disparity and (3) as in (2) but with a time-continuous update to \begin{document}$R_t(n)$\end{document}. We make a study of 9 U.S. states and the District of Columbia providing a complete time series of the pandemic in each and, in some cases, identifying disparities not otherwise evident in the aggregate statistics.

    « less
  4. 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}.

  5. Stochastic differential games have been used extensively to model agents' competitions in finance, for instance, in P2P lending platforms from the Fintech industry, the banking system for systemic risk, and insurance markets. The recently proposed machine learning algorithm, deep fictitious play, provides a novel and efficient tool for finding Markovian Nash equilibrium of large \begin{document}$ N $\end{document}-player asymmetric stochastic differential games [J. Han and R. Hu, Mathematical and Scientific Machine Learning Conference, pages 221-245, PMLR, 2020]. By incorporating the idea of fictitious play, the algorithm decouples the game into \begin{document}$ N $\end{document} sub-optimization problems, and identifies each player's optimal strategy with the deep backward stochastic differential equation (BSDE) method parallelly and repeatedly. In this paper, we prove the convergence of deep fictitious play (DFP) to the true Nash equilibrium. We can also show that the strategy based on DFP forms an \begin{document}$ \epsilon $\end{document}-Nash equilibrium. We generalize the algorithm by proposing a new approach to decouple the games, and present numerical results of large population games showing the empirical convergence of the algorithm beyond the technical assumptions in the theorems.