Free Lunch for optimisation under the universal distribution

Tom Everitt*, Tor Lattimore, Marcus Hutter

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    10 Citations (Scopus)

    Abstract

    Function optimisation is a major challenge in computer science. The No Free Lunch theorems state that if all functions with the same histogram are assumed to be equally probable then no algorithm outperforms any other in expectation. We argue against the uniform assumption and suggest a universal prior exists for which there is a free lunch, but where no particular class of functions is favoured over another. We also prove upper and lower bounds on the size of the free lunch.

    Original languageEnglish
    Title of host publicationProceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages167-174
    Number of pages8
    ISBN (Electronic)9781479914883
    DOIs
    Publication statusPublished - 16 Sept 2014
    Event2014 IEEE Congress on Evolutionary Computation, CEC 2014 - Beijing, China
    Duration: 6 Jul 201411 Jul 2014

    Publication series

    NameProceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014

    Conference

    Conference2014 IEEE Congress on Evolutionary Computation, CEC 2014
    Country/TerritoryChina
    CityBeijing
    Period6/07/1411/07/14

    Fingerprint

    Dive into the research topics of 'Free Lunch for optimisation under the universal distribution'. Together they form a unique fingerprint.

    Cite this