Continuous lunches are free plus the design of optimal optimization algorithms

Anne Auger 1, 2 Olivier Teytaud 1, 2, 3
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
2 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 : This paper analyses extensions of No-Free-Lunch (NFL) theorems to countably infinite and uncountable infinite domains and investigates the design of optimal optimization algorithms. The original NFL theorem due to Wolpert and Macready states that, for finite search domains, all search heuristics have the same performance when averaged over the uniform distribution over all possible functions. For infinite domains the extension of the concept of distribution over all possible functions involves measurability issues and stochastic process the- ory. For countably infinite domains, we prove that the natural extension of NFL theorems, for the current formalization of probability, does not hold, but that a weaker form of NFL does hold, by stating the existence of non-trivial distributions of fitness leading to equal performances for all search heuristics. Our main result is that for continuous domains, NFL does not hold. This free-lunch theorem is based on the formalization of the concept of random fitness functions by means of random fields. We also consider the design of optimal optimization algorithms for a given random field, in a black-box setting, namely, a complexity measure based solely on the number of requests to the fitness function. We derive an optimal algorithm based on Bellman's decomposition principle, for a given number of iterates and a given distribution of fitness functions. We also approximate this algorithm thanks to a Monte-Carlo planning algorithm close to the UCT (Upper Confidence Trees) algorithm, and provide experimental results.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2009, 〈10.1007/s00453-008-9244-5〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00369788
Contributeur : Olivier Teytaud <>
Soumis le : samedi 21 mars 2009 - 10:09:49
Dernière modification le : jeudi 10 mai 2018 - 02:06:59
Document(s) archivé(s) le : jeudi 10 juin 2010 - 17:59:17

Fichier

ccflRevisedVersionAugerTeytaud...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Anne Auger, Olivier Teytaud. Continuous lunches are free plus the design of optimal optimization algorithms. Algorithmica, Springer Verlag, 2009, 〈10.1007/s00453-008-9244-5〉. 〈inria-00369788〉

Partager

Métriques

Consultations de la notice

422

Téléchargements de fichiers

334