Answers are grounded in this paper and cite their sources.
This analysis uncovers the average number of steps required in stochastic optimisation, highlighting the role of random walks and probability distributions.
Random walks are considered in a one-dimensional monotonously decreasing energy landscape. To reach the minimum within a region Ωϵ, a number of downhill steps have to be performed. A stochastic model is proposed which captures this random downhill walk and to make a prediction for the average number of steps, which are needed to hit the target. Explicit expressions in terms of a recurrence relation are derived for the density distribution of a downhill random walk as well as probability distribution functions to hit a target region Ωϵ within a given number of steps. For the case of stochastic optimisation, the number of rejected steps between two successive downhill steps is also derived, providing a measure for the average total number of trial steps. Analytical results are obtained for generalised random processes with underlying polynomial distribution functions. Finally the more general case of non-monotonously decreasing energy landscapes is considered for which results of the monotonous case are transferred by applying the technique of decreasing rearrangement. It is shown that the global stochastic optimisation can be fully described analytically, which is verified by numerical experiments for a number of different distribution and objective functions. Finally we discuss the transition to higher dimensional objective functions and discuss the change in computational complexity for the stochastic process.
No takes yet. Share an insight, caveat, or question.
Godehard Sutmann (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: