Re-use of samples in stochastic annealing

The re-use of samples in stochastic black box optimisation is a double-edged sword. On the one hand it has the potential of substantially reducing the number of simulation runs required, on the other hand it introduces dependencies between iterations of the optimisation algorithm that may misguide the search. This paper proposes a principled way to re-use samples in stochastic annealing, a generalisation of simulated annealing for stochastic black-box optimisation problems. We propose three alternative algorithms that all, despite the stochastic errors when evaluating a solution via simulation, obey the detailed balance equation and thus have the same assurance of converging to the true optimum as standard simulated annealing in the deterministic case. This is achieved by optimising in the product space of solution and error. We compare our new algorithms in terms of their acceptance ratio as well as empirically on two stochastic combinatorial optimisation problems and find that the best algorithms are of order twice as efficient as the state-of-the-art. Furthermore, one algorithm we propose can work with non-Gaussian and even unknown error distributions.