Lower Bounds for Evolution Strategies
Résumé
The mathematical analysis of optimization algorithms involves upper and lower bounds; we here focus on the second case. Whereas other chap- ters will consider black box complexity, we will here consider complexity based on the key assumption that the only information available on the fitness values is the rank of individuals - we will not make use of the exact fitness values. Such a reduced information is known efficient in terms of ro- bustness (Gelly et al., 2007), what gives a solid theoretical foundation to the robustness of evolution strategies, which is often argued without mathemat- ical rigor - and we here show the implications of this reduced information on convergence rates. In particular, our bounds are proved without infi- nite dimension assumption, and they have been used since that time for designing algorithms with better performance in the parallel setting.
Domaines
Optimisation et contrôle [math.OC]
Origine : Fichiers produits par l'(les) auteur(s)