Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

From Wikipedia about interpretations of no free lunch theorem

A conventional, but not entirely accurate, interpretation of the NFL results is that "a general-purpose universal optimization strategy is theoretically impossible, and the only way one strategy can outperform another is if it is specialized to the specific problem under consideration".[14] Several comments are in order:

A general-purpose almost-universal optimizer exists theoretically. Each search algorithm performs well on almost all objective functions.[11]

...

For almost all objective functions, specialization is essentially accidental. Incompressible, or Kolmogorov random, objective functions have no regularity for an algorithm to exploit. Given an incompressible objective function, there is no basis for choosing one algorithm over another. If a chosen algorithm performs better than most, the result is happenstance.[11]

I was wondering

  1. How shall I understand that a general-purpose universal optimizer doesn't exist but a general-purpose almost universal optimizer does? What differences are between universal and almost universal?
  2. Do the last two sentences in bold contradict each other? Do "an optimizer being almost-universal and perform well on all objective functions" and "it being specialized for almost all objective functions" imply each other?

Thanks and regards!

share|improve this question
    
You may want to take the question to brand-new cs.SE! –  Raphael Mar 23 '12 at 23:31
    
Thanks! Is it too theoretical for that new site? –  Tim Mar 23 '12 at 23:54
    
Not at all, we span all CS. –  Raphael Mar 24 '12 at 11:55
    
Is that an 'almost' full employment theorem? –  Trevor Alexander Mar 1 '13 at 9:30

1 Answer 1

The first quote should not have been published, because the conclusion is categorically wrong. Almost all objective functions are Kolmogorov random. They have no order whatsoever that can be exploited in optimizer design. An optimizer cannot be specialized to one of them. For almost all of the theoretically possible functions on which an optimizer performs well (or poorly), performance has absolutely nothing to do with specialization (or lack thereof).

  1. There is "no free lunch" when the optimization result does not, as far as the practitioner can tell, depend on the choice of sampler. This does not mean that the optimization result is bad. When all objective functions are equally likely, modest-sized samples of the objective function, drawn uniformly at random, almost always contain a good value. Because drawing a sample uniformly at random is equivalent to drawing a deterministic (non-random) algorithm uniformly at random, and then applying it, almost all deterministic algorithms perform well on each objective function. See Table 1, p. 16, of the emended version of my first NFL paper (1996).

  2. The last boldface sentence is self-contradictory, and should be deleted. What I have written here explains why, as do the sentences following it in the article.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.