Fast simulated annealing in \R^d and an application to maximum likelihood estimation

2006/09/13 by Sylvain Rubenthaler, Rubenthaler, Sylvain, Tobias Rydén +3
Computer Science · #Bayesian Methods and Mixture Models #Machine Learning and Algorithms #Blind Source Separation Techniques

paper · pdf · doi:10.48550/arxiv.math/0609353

Abstract

Using classical simulated annealing to maximise a function ψ defined on a subset of \R^d, the probability \p(ψ(θ_n)≤ ψ_max-ε) tends to zero at a logarithmic rate as n increases; here θ_n is the state in the n-th stage of the simulated annealing algorithm and ψ_max is the maximal value of ψ. We propose a modified scheme for which this probability is of order n^-1/3log n, and hence vanishes at an algebraic rate. To obtain this faster rate, the exponentially decaying acceptance probability of classical simulated annealing is replaced by a more heavy-tailed function, and the system is cooled faster. We also show how the algorithm may be applied to functions that cannot be computed exactly but only approximated, and give an example of maximising the log-likelihood function for a state-space model.

Related

• An improved variant of simulated annealing that converges under fast cooling
• Improving Simulated Annealing through Derandomization
• Convergence theorems for a class of simulated annealing algorithms on ℝd
• Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers law
• Convergence rate of a simulated annealing algorithm with noisy observations