Log-log Convergence for Noisy Optimization

Sandra Cecilia Astete-Morales 1, 2 Jialin Liu 1, 2 Olivier Teytaud 2, 1
1 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : We consider noisy optimization problems, without the as-sumption of variance vanishing in the neighborhood of the optimum. We show mathematically that simple rules with exponential number of re-samplings lead to a log-log convergence rate. In particular, in this case the log of the distance to the optimum is linear on the log of the num-ber of resamplings. As well as with number of resamplings polynomial in the inverse step-size. We show empirically that this convergence rate is obtained also with polynomial number of resamplings. In this polyno-mial resampling setting, using classical evolution strategies and an ad hoc choice of the number of resamplings, we seemingly get the same rate as those obtained with specific Estimation of Distribution Algorithms de-signed for noisy setting. We also experiment non-adaptive polynomial re-samplings. Compared to the state of the art, our results provide (i) proofs of log-log convergence for evolution strategies (which were not covered by existing results) in the case of objective functions with quadratic expec-tations and constant noise, (ii) log-log rates also for objective functions with expectation E[f (x)] = ||x − x * || p , where x * represents the optimum (iii) experiments with different parametrizations than those considered in the proof. These results propose some simple revaluation schemes. This paper extends [1].
Type de document :
Communication dans un congrès
Evolutionary Algorithms 2013, Oct 2013, Bordeaux, France. pp.16 - 28, 2014, Proceedings of EA 2013. 〈10.1007/978-3-319-11683-9_2〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01107772
Contributeur : Olivier Teytaud <>
Soumis le : lundi 19 octobre 2015 - 10:06:15
Dernière modification le : vendredi 23 février 2018 - 13:42:26
Document(s) archivé(s) le : jeudi 27 avril 2017 - 06:02:55

Fichier

paperhal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Sandra Cecilia Astete-Morales, Jialin Liu, Olivier Teytaud. Log-log Convergence for Noisy Optimization. Evolutionary Algorithms 2013, Oct 2013, Bordeaux, France. pp.16 - 28, 2014, Proceedings of EA 2013. 〈10.1007/978-3-319-11683-9_2〉. 〈hal-01107772v2〉

Partager

Métriques

Consultations de la notice

180

Téléchargements de fichiers

106