Analysis of runtime of optimization algorithms for noisy functions over discrete codomains

Youhei Akimoto 1 Sandra Astete-Morales 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 in this work the application of optimization algorithms to problems over discrete codomains corrupted by additive unbiased noise. We propose a modification of the algorithms by repeating the fitness evaluation of the noisy function sufficiently so that, with a fix probability, the function evaluation on the noisy case is identical to the true value. If the runtime of the algorithms on the noise-free case is known, the number of resampling is chosen accordingly. If not, the number of resampling is chosen regarding to the number of fitness evaluations, in an anytime manner. We conclude that if the additive noise is Gaussian, then the runtime on the noisy case, for an adapted algorithm using resamplings, is similar to the runtime on the noise-free case: we incur only an extra logarithmic factor. If the noise is non-Gaussian but with finite variance, then the total runtime of the noisy case is quadratic in function of the runtime on the noise-free case.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2015, 605, pp.42:50. 〈10.1016/j.tcs.2015.04.008〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01194556
Contributeur : Olivier Teytaud <>
Soumis le : lundi 7 septembre 2015 - 11:26:52
Dernière modification le : jeudi 17 mai 2018 - 12:52:03
Document(s) archivé(s) le : mardi 8 décembre 2015 - 11:53:27

Fichier

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

Identifiants

Citation

Youhei Akimoto, Sandra Astete-Morales, Olivier Teytaud. Analysis of runtime of optimization algorithms for noisy functions over discrete codomains. Theoretical Computer Science, Elsevier, 2015, 605, pp.42:50. 〈10.1016/j.tcs.2015.04.008〉. 〈hal-01194556〉

Partager

Métriques

Consultations de la notice

523

Téléchargements de fichiers

269