A Rigorous Runtime Analysis for Quasi-Random Restarts and Decreasing StepsizeReport as inadecuate

A Rigorous Runtime Analysis for Quasi-Random Restarts and Decreasing Stepsize - Download this document for free, or read online. Document in PDF available to download.

1 TAO - Machine Learning and Optimisation LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623 2 MSR - INRIA - Microsoft Research - Inria Joint Centre 3 LRI - Laboratoire de Recherche en Informatique

Abstract : Multi-Modal Optimization MMO is ubiquitous in engineer- ing, machine learning and artificial intelligence applications. Many algo- rithms have been proposed for multimodal optimization, and many of them are based on restart strategies. However, only few works address the issue of initialization in restarts. Furthermore, very few comparisons have been done, between different MMO algorithms, and against simple baseline methods. This paper proposes an analysis of restart strategies, and provides a restart strategy for any local search algorithm for which theoretical guarantees are derived. This restart strategy is to decrease some -step-size-, rather than to increase the population size, and it uses quasi-random initialization, that leads to a rigorous proof of improve- ment with respect to random restarts or restarts with constant initial step-size. Furthermore, when this strategy encapsulates a 1+1-ES with 1-5th adaptation rule, the resulting algorithm outperforms state of the art MMO algorithms while being computationally faster.

Author: Marc Schoenauer - Fabien Teytaud - Olivier Teytaud -

Source: https://hal.archives-ouvertes.fr/


Related documents