Estimating the Convergence Rate of a Restarted Search Process
Xiaohua Hu, Ronald W. Shonkwiler, M. C. Spruill · 2000
When a deterministic algorithm for finding the minimum of a function C on a set Ω is em-ployed it may reach a local, non-global, minimum of C and remain there forever after. Restarting repeatedly and independently by a random choice of a starting point in Ω when the algorithm reaches a settling point engenders a probability of λn/s, where λ ∈ (0, 1), of not having seen the goal state by the nth epoch. The rate λ may be expressed precisely, if only theoretically, as the solution to the equation λ−1φH|N (λ−1) = (1 − θ0)−1 where φH|N is the probability generating function of the random time for the algorithm to reach a settling point given that the starting state is one which leads to a non-global extremum. Here, θ0 is the probability of a random start leading directly to the goal without any restart required and in problems of interest will be quite small. A simple bound has λ> (1−θ0)(1+E[H|N])θ0+(1−θ0)(1+E[H|N]) so that slow geometric rates of convergence in problems for which θ0 is small are even slower when there are large expected times between restarts in non-goal states. Nevertheless, geometric rates imply that independent identical parallel processing has potential benefits in speeding up acquisition of the goal states and the expression of the precise rate in terms of the probability generating function of the random times to restart in non-goal states provides a method of statistical estimation of the probability of having not yet seen the goal state and an estimate obtained on the fly of the resources required to obtain an answer by a prescribed time.