Performance analysis of the simultaneous perturbation stochastic approximation algorithm on the noisy sphere model

摘要

To theoretically compare the behavior of different algorithms, compatible performance measures are necessary. Thus in the first part, an analysis approach, developed for evolution strategies, was applied to simultaneous perturbation stochastic approximation on the noisy sphere model. A considerable advantage of this approach is that convergence results for non-noisy and noisy optimization can be obtained simultaneously. Next to the convergence rates, optimal step sizes and convergence criteria for 3 different noise models were derived. These results were validated by simulation experiments. Afterward, the results were used for a comparison with evolution strategies on the sphere model in combination with the 3 noise models. It was shown that both strategies perform similarly, with a slight advantage for SPSA if optimal settings are used and the noise strength is not too large.