Rough large deviation estimates for the optimal convergence speed exponent of generalized simulated annealing algorithms (Q1917689)

The author introduces the notion of generalized simulated annealing that covers, e.g., versions of parallel sequential annealing. Various results of \textit{O. Catoni} [Ann. Probab. 20, No. 3, 1109-1146 (1992; Zbl 0755.60021)] on convergence and large deviation of sequential annealing schemes are transferred and proved in this generalized framework. In particular, the following setting is considered: Let \(E\) be a finite set, \(\kappa\in [0, \infty]\), \(q(.,.)\) an irreducible Markov kernel on \(E\), \(\{Q_t (.,.) \}_{t\geq 0}\) a family of Markov kernels such that \[ \kappa^{-1} q(i, j)e^{-V (i,j)/t} \leq Q_t (i, j)\leq \kappa q(i, j) e^{-V (i,j) /t} \] for any \(V: E\times E\to [0, \infty]\) which is finite if \(q(i, j)> 0\). Then the coordinate process \(\{X_n \}_{n\in \mathbb{N}}\) in \(E^\mathbb{N}\) is called generalized simulated annealing process, if there is a family \(\{Q_t (.,.) \}_{t\geq 0}\) (as above), a sequence \(\{T_n \}_{n\in \mathbb{N}} \subset \mathbb{R}_+\), and an initial distribution \(\nu_0\) such that \(\mathbb{P}_{(Q_t, T_n, \nu_0)}\) is the unique probability measure on \(E^\mathbb{N}\) that turns \(\{X_n \}_{n\in \mathbb{N}}\) into a Markov chain with respect to its natural filtration, initial distribution \(\nu_0\), and transition kernels \(Q_{T_n} (.,.)\) at time \(n\). In this situation, a large deviation principle for the exit time of arbitrary subsets and generalized simulated annealing is proved. The estimates hold uniformly with respect to the cooling scheme \(\{T_n \}_{n\in \mathbb{N}}\). The technique of the proof follows Catoni's approach but is also based on a renormalization of the function \(V(.,.)\) which makes it possible to consider both arbitrary sets and generalized annealing. Necessary and sufficient conditions for the convergence of the annealing schemes (similar to those of the sequential case) are given. Under some additional conditions on \(\{Q_t \}_{t\geq 0}\) and \(\{T_n \}_{n\in \mathbb{N}}\) the optimal convergence speed coefficient is explicitly computed thus settling a conjecture of \textit{R. Azencott} [in: Simulated annealing. Parallelization techniques, 11-23 (1992; Zbl 0787.90072)].