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
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [40 references]  Display  Hide  Download

https://hal.inria.fr/inria-00369788
Contributor : Olivier Teytaud <>
Submitted on : Saturday, March 21, 2009 - 10:09:49 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on : Thursday, June 10, 2010 - 5:59:17 PM

File

ccflRevisedVersionAugerTeytaud...
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

546

Files downloads

480