scientific article; zbMATH DE number 1746624
The authors of this interesting paper investigate the statistical properties of the progress towards the minimum for a class of stochastic algorithms. When a deterministic algorithm for finding the minimum of a function on a set is employed, it may reach a local minimum and remain there forever after. Restarting repeatedly and independently by a random choice of a starting point when the algorithm reaches a settling point engenders a probability of \(\lambda^n/s\) of not having seen the goal state by the \(n\)th epoch. \textit{R. Shonkwiler} and \textit{E. Van Vleck} [J. Complexity 10, No. 1, 64-95 (1994; Zbl 0798.90124)] studied restarting from the perspective of its consequence on first hitting times. The present results extend those of Shonkwiler and Van Vleck and introduce on-the-fly estimation of the rate of convergence of the algorithm and prove its asymptotic normality. The elements of the class of stochastic algorithms treated here are generated by randomly restarting a deterministic iterative scheme when it reaches a settling point. Given a real valued function \(C\) defined on a topological domain \(\Omega \) with neighborhood system \(N\), restart methods for finding some point \(x^{\ast }\in opt (C)=G\) are analyzed. The set of global minimizers of \(C\) over \(\Omega \), where \(x^{\ast }\in G\) entails \(C(x^{\ast })\leq C(x)\), \(x\in \Omega \) is analyzed as well. In case \(C\) is sufficiently smooth, there are powerful numerical methods for finding local minimizers. Assume \(M\) is the union of all the basins whose settling points are global minima. Then the number \(T=\min \{t:X(t)\in M\}\) (the first hitting time of \(M\) by the search process) would be of primary interest. The main result is that if \(\mu \) places positive mass at all points of the finite set \(\Omega \), then there are \(\lambda \in (0,1)\), \(\delta \in (0,\lambda)\), and a constant \(s>1\) such that for any \(\varepsilon >0\) there exists \((\delta +\varepsilon)^{-n}|P[T>n]-\lambda^n/s|\to 0\) as \(n\to \infty \). It turns out that \(\lambda \) is the unique positive solution to the equation \(\lambda^{-1}\phi_{H|N}(\lambda^{-1})=(1-\theta_0)^{-1}\), where \(\phi_{H|N}\) is the probability generating function of the random time to first settling point given that the starting state is one which leads to a non-global extremum. Results on expectation of time to hit the goal are presented as well. The consequences of independent identical processing, and how to estimate the parameter \(\lambda \) on the fly are also discussed.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4530783)